Automata Theory 简明教程

Pushdown Automata Introduction

Basic Structure of PDA

下推自动机是一种以与我们为正规语法设计DFA类似的方式实现无上下文语法的途径。一个DFA可以记忆有限量的信息，而一个PDA可以记忆无限量的信息。

基本上，下推自动机为 −

"Finite state machine" + "a stack"

一个下推自动机有三个组件 −

  1. an input tape,

  2. a control unit, and

  3. 具有无限大小的栈。

栈头扫描栈的顶端符号。

栈执行两种操作 −

  1. Push − 在顶部添加一个新的符号。

  2. Pop − 读取并移除顶端符号。

一个PDA可以读取或不读取一个输入符号，但它必须在每个转换中读取栈的顶部。

pda

PDA 可以形式化描述为一个 7 元组 (Q, ∑, S, δ, q0, I, F)

  1. Q 是有限状态数

  2. ∑ is input alphabet

  3. S is stack symbols

  4. δ 是转换函数：Q × (∑ ∪ {ε}) × S × Q × S*

  5. q0 是初始状态（q0 ∈ Q）

  6. I 是初始栈顶符号（I ∈ S）

  7. F 是接受状态的集合（F ∈ Q）

下图展示了一个 PDA 从一个状态 q1 到状态 q2 的转换，标记为 a,b → c

transition in a pda

这意味着在状态 q1 ，如果我们遇到一个输入字符串 ‘a’ 且栈顶符号是 ‘b’ ，则我们弹出 ‘b’ ，入栈 ‘c’ 至栈顶，并移至状态 q2 。

Terminologies Related to PDA

Instantaneous Description

PDA 的瞬时描述（ID）由三元组 (q, w, s) 表示，其中

  1. q is the state

  2. w is unconsumed input

  3. s 是栈内容

Turnstile Notation

“turnstile”符号用于连接表示 PDA 的一次或多次移动的 ID 对。转换过程由 turnstile 符号“⊢”表示。

考虑一个 PDA (Q, ∑, S, δ, q0, I, F)。一个转换可以用下面的 turnstile 符号以数学方式表示

(p, aw, Tβ) ⊢ (q, w, αb)

这表示在从状态 p 转换到状态 q 时，消耗了输入符号 ‘a’ ，且栈顶 ‘T’ 被一个新字符串 ‘α’ 替换。

Note - 如果希望 PDA 的移动次数为零或更多，则必须使用符号 (⊢*)。