形式语言与自动机理论-07-下推自动机

下推自动机(Pushdown Automata, PDA)在有限状态自动机的基础上增加了一个可读写的栈,其中状态转移函数在匹配输入字符串的下一个字符之外还需匹配栈顶符号,并且可选地从栈顶移除/向栈顶写入任意多个字符。计算开始时栈为空,并在原先接受条件的基础上要求栈为空。

形式化地,定义下推自动机 \(G\) 为元组 \((Q, \Sigma, \Gamma, \delta, q_0, Q_{acc})\)

其中 \(Q\), \(\Sigma\), \(q_0\), \(Q_{acc}\) 的定义及意义与它们在 FSA 中的相同。

\(\Gamma\) 为与 \(\Sigma\) (不失一般性地)不交的有限集合,称为栈字符集。同时称 \(\Sigma\) (前称字符集)为输入字符集以明示区别。

另有符号 \(\varepsilon \not\in \Gamma\)\(\Gamma^0\) 的唯一元素作为唯一零长度的栈字符串。我们以 \(\varepsilon\) 同时记零长栈字符串及零长输入字符串,并由上下文来做区分。

\(\delta\)\(Q \times (\Sigma \cup \{\varepsilon\}) \times (\Gamma \cup \{\varepsilon\}) \times Q \times \Gamma^*\) 上的关系。称元素 \((p, a, A, q, B) \in \delta\)\(G\) 的一个转移,其表示若 \(G\) 当前的状态为 \(p\),下一个输入字符为 \(a\),栈顶有符号 \(A\),则 \(G\) 应读入 \(a\),出栈 \(A\),状态转移至 \(q\),并入栈字符串 \(B\)

在用图表示 PDA 时,对于每一个 \((p, a, A, q, B) \in \delta\),添加自节点 \(p\) 至节点 \(q\) 的有向边并以 \(a, A \mapsto B\) 标记该边。

若对于任何 \(p \in Q\), \(a \in \Sigma\), \(A \in \Gamma\), 至多仅分别有一个 \(q \in Q\), \(B \in \Gamma^*\),使得

\[ (p, a, \varepsilon, q, B) \in \delta \\ (p, \varepsilon, A, q, B) \in \delta \]

中仅有一项成立,则称 PDA \(G\) 为确定性下推自动机(DPDA),这样的情况下有时也将 \(\delta\) 当做 \(Q \times (\Sigma \cup \{\varepsilon\}) \times (\Gamma \cup \{\varepsilon\}) \to Q \times \Gamma^*\) 类型的函数使用(注意,并非所有该类型的函数都符合上述条件)。否则称 \(G\) 为非确定性下推自动机(NPDA)。

有时可见其他类似的定义,如 \(\delta \subseteq Q \times \Sigma^* \times \Gamma^* \times Q \times \Gamma^*\)。通常来说1,类似的定义都是等价的。

\(\newcommand{\step}{\vdash_G}\) \(\newcommand{\steps}{\step^*}\)

定义 \((Q, \Sigma^*, \Gamma^*)^2\) 上的中缀二元关系 \(\step\) 为满足以下要求的最小集合:

\[ (p, a, A, q, B) \in \delta \iff (p, a\omega, A\gamma) \step (q, \omega, B\gamma) \]

定义 \(\steps\)\(\step\) 的自反传递封闭。

于是定义在 \(\Sigma\) 上的字符串 \(s\) 被自动机 \(G\) 识别,若有 \((q_0, s, \varepsilon) \steps (q, \varepsilon, \varepsilon)\),其中 \(q \in Q_{acc}\).

于是可定义下推自动机 \(G\) 识别的语言为

\[ L(G) := \{s \in \Sigma^* : (q_0, s, \varepsilon) \steps (q_m, \varepsilon, \varepsilon), q \in Q_{acc}\} \]

下述下推自动机识别语言 \(L = \{a^ib^i | i \ge 0\}\).

该自动机是确定的。

下述下推自动机识别语言 \(L = \{a^ib^i | i \ge 0\} \cup \{a^2b^i | i \ge 0\}\).

该自动机是非确定的,并且不存在识别该语言的确定性下推自动机。

有证明表示,任何上下文无关语法描述的语言皆有识别其的下推自动机。另对于任何下推自动机,皆有描述其所识别的语言的上下文无关语法。

有证明表示,确定性下推自动机所识别的语言严格子集于非确定性下推自动机所识别的语言。因此不存在用于下推自动机的确定化算法。


  1. 例如,需要允许不读入字符,不出栈字符,不入栈字符↩︎