7.1. 下推自动机¶
7.1.1. 下推自动机¶
回顾（recall）：一个 DFA \(=(Q, \Sigma, \delta, q_0, F)\) 。
DFA 示例
在 DFA 中，带（tape）只读，读写头（head）只能向右移动。 DFA 的能力是有限的。它们能识别正则语言，但无法识别许多其他"简单"的语言，例如 \(a^nb^n\) 。
现在，我们将给 DFA 加上一个栈（stack）。这种新机器称为下推自动机（Pushdown Automata，PDA）。显然，它之所以得到这个名字，正是因为它具有新的能力——把符号 下推（pushdown） 并存储到栈上。这增加了一种额外内存（memory）的形式，使机器能够把数据存到栈上，并从栈中取出数据。
PDA 示例
原有的限制仍然适用：带只读，读写头只能向右移动。
回顾一下，我们曾可以把非确定性的概念加到 DFA 上。事实证明，这并不会改变 DFA 能识别的语言集合。那么，如果我们把非确定性加到 PDA 上，又会怎样呢？
定义（Definition）： 一个非确定性的 PDA（nondeterministic PDA，NPDA）定义为 \(M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)\) ，其中
\(Q\) 是状态的有限集合\(\Sigma\) 是带（输入）字母表（一个有限集合）\(\Gamma\) 是栈字母表（一个有限集合）\(q_0\) 是初始状态，\(q_0 \in Q\)\(z\) 是起始栈符号 （标记栈底），\(z \in \Gamma\)\(F \subseteq Q\) 是最终状态的集合。\(\delta : Q \times (\Sigma \cup \{\lambda\}) \times \Gamma \rightarrow\) \(Q \times \Gamma^*\) 的有限子集
转移函数 \(\delta\) 是一个映射，其像为 \(Q \times \Gamma^*\) 的有限子集。
7.1.1.1. 转移示例¶
\(\delta(q_1, a, b) = \{(q_3, b),(q_4, ab), (q_6, \lambda)\}\)
含义：如果在状态 \(q_1\) ，当前带符号是 a ，栈顶符号是 b ，则弹出 b ，然后要么
转移到 \(q_3\) 并把b压入栈转移到 \(q_4\) 并把ab压入栈（a在栈顶）转移到 \(q_6\)
转移可以用转移图（transition diagram）来表示。上述转移所对应的图为：
每条弧用一个三元组 \(<x, y; z>\) 标记，其中 \(x\) 是当前输入符号，\(y\) 是从栈中弹出的栈顶符号，\(z\) 是被压入栈的字符串。
瞬时描述（Instantaneous Description）： \((q, w, u)\)
这是用来描述机器状态的记号：机器的当前状态为 \(q\)，输入字符串尚未读过的部分为 \(w\)，栈的当前内容为 \(u\)。（在 JFLAP 中，这称为一个构形（configuration）。）
一次移动的描述（Description of a Move）：
定义（Definition）： 设 \(M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)\) 是一个 NPDA。 \(L(M) = \{w \in \Sigma^* | (q_0, w, z) \stackrel{*}{\vdash} (p, \lambda, u), p \in F, u \in \Gamma^*\}\)。 NPDA 接受所有从 \(q_0\) 出发并在最终状态结束的字符串。
注（NOTE）：如果机器以最终状态结束对字符串的处理，则栈的内容无关紧要。
让我们看看接受字符串 $aaabbb$ 的跟踪过程。
另一种语言接受定义（Another Definition for Language Acceptance）： NPDA \(M\) 通过空栈接受 \(L(M)\) ：
\(L(M) = \{w \in \Sigma^* | (q_0, w, z) \stackrel{*}{\vdash} (p, \lambda, \lambda)\}\)
注（NOTE）：上面的三元组是构形。机器从一个构形移动到另一个构形。
L 不是 CFL，因此不存在 NPDA！
供你自行练习的示例（Examples for you to try on your own）： （解答位于本节末尾）。
\(L = \{a^nb^m | m > n, m, n > 0\}, \Sigma = \{a, b\}, \Gamma = \{z, a\}\)
\(L = \{a^nb^{n+m}c^m | n, m> 0\}, \Sigma=\{a, b, c\}\)
\(L = \{a^nb^{2n} | n > 0\}, \Sigma=\{a,b\}\)
提醒（Reminder）： 接受的定义是，如果我们以最终状态结束对字符串的处理，则接受。栈的内容无关紧要。
定义（Definition）： 一个 PDA \(M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)\) 是 确定性的（deterministic） ，如果对每一个 \(q \in Q, a \in \Sigma \cup \{\lambda\}, b \in \Gamma\)
\(\delta(q, a, b)\) 至多包含 1 个元素
如果 \(\delta(q, \lambda, b) \neq \emptyset\) ，则对所有 \(c \in \Sigma\) 都有 \(\delta(q, c, b) = \emptyset\) 。
定义： \(L\) 是 DCFL 当且仅当 \(\exists\) DPDA \(M\) 使得 \(L = L(M)\) 。
示例（Examples）：
之前用于 \(\{a^nb^n | n\ge 0\}\) 的 PDA 是确定性的。
之前用于 \(\{a^nb^mc^{n+m} | n, m> 0\}\) 的 PDA 很可能是确定性的。
之前用于 \(\{ww^R | w \in \Sigma^+\}, \Sigma = \{a, b\}\) 的 PDA 是非确定性的。
7.1.1.2. 接受定义的等价性¶
定理 给定以终态方式接受的 NPDA M，存在（ \(\exists\) ）以空栈方式接受的 NPDA \(M'\) ，使得 \(L(M) = L(M')\) 。
证明（Proof）（概要）
\(M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)\)构造 \(M' = (Q', \Sigma, {\Gamma}^{'}, {\delta}^{'}, q_s, z', F')\) （注：\(z'\) 是一个新符号）\(Q' = Q \cup \{q_s, q_f\}\)\({\Gamma}^{'} = \Gamma \cup \{z'\}\) （注：\(z' \not\in \Gamma\) ，在原机器中从未被弹出）\(q_s\) 是新的起始状态。\(F = \{\}\) 。无关紧要。 栈只有在 \(q_f\) 中才会为空。这里，\(x\) 是 \({\Gamma}^{'}\) 中的任意符号。 （\(l\) 表示 \(\lambda\)。）在这种情况下，实际上并不需要最终状态的概念。证毕（QED）。
定理： 给定以空栈方式接受的 NPDA \(M\) ，存在（ \(\exists\) ）以终态方式接受的 NPDA \(M'\) 。
证明（Proof）：
\(M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)\)构造 \(M' = (Q', \Sigma, \Gamma^{'}, \delta^{'}, q_s, z', F')\)\(Q' = Q \cup \{q_s, q_f\}\)\(\Gamma^{'} = \Gamma \cup \{z'\}\)\(q_s\) 是新的起始状态。\(F^ = \{q_f\}\)。 栈只有在 \(q_f\) 中才会为空。对所有 \(q \in Q\) ：\((q_f, z') \in \delta(q, \lambda, z')\)。如果 \(M\) 在某个状态下接受，那就意味着栈为空。 在 \(M'\) 中，在相同的状态下，栈中将只包含 \(z'\) ，于是可以顺着新的转移到达 \(q_f\)。证毕（QED）。
