计算理论：下推自动机

course notes › theory of computation

Pushdown Automata

Definition

Informal: PDA is a -NFA with a stack

Formal: A PDA is a 7-tuple, where

  • : a finite set of states
  • : a finite set of input symbols
  • : a finite stack alphabet
  • : the transition function
  • : the start state
  • : the start symbol in stack
  • : the set of accepting states

考虑 PDA 的迁移函数 ，其接受三个参数 ，其中

  • 是 中的状态
  • 是 中的符号或是
  • 是 中的符号

其输出为有序对 的集合，其中 是一个新状态，而 是一个 stack symbol 的 string，用于取代 。当 ，表示弹出 ，而当 则不变，若 ，则将 替换为 ，再将 压入。

PDA 也可以像 FA 一样使用图表示，其中

  • 节点代表 PDA 的 states
  • 两个圈的节点表示接收状态
  • 一条标号为 的从 到 的边表示

不同于 FA，描述状态机的运行的只有状态，PDA 的运行包括了状态与栈的内容，故定义 Instantaneous Description 为一个 3-tuple

  • 是一个状态
  • 是余下的输入
  • 是栈的内容

PDA 的 ID 可以完全表示其运行时某一个时刻的格局。

为了描述 ID 随着 PDA 的运行而发生的转换，定义 。若 包含 ，则对于任意 有

显然，余下的输入和栈中剩余的部分不影响 ID 的转换

表示 PDA 的一步动作，可以定义 表示 0 步或多步动作

Basis. for any ID

Induction. If , then

对于 ID 的 transition，有

If is a PDA, and , then for any strings and , it is also true that

Proof.

对 ID 的转换步数归纳。由于 PDA 未读入的输入不会影响其行为，故在输入后添加后缀 不会改变其行为。同样的，在原本的转换中，没有用到 以外的内容，故在栈底加入 也不会改变其行为

Q.E.D.

同样的，有

If is a PDA, and

then

需要注意的是未读入的输入不会对 PDA 产生影响，故可以将其共同的后缀去除，但是不能将栈共同的后缀去除。考虑转换前栈中为 ，转换后为 ，在转换的过程中可能弹出了 中的符号，然后之后又将其压入，若将 去除则转换不能成立

添加或删除输入串的后缀不影响转换，但只能添加栈底内容而不能删除

The Language of a PDA

有两种方式可以让一个 PDA 接受输入

  • acceptance by final state: 当输入结束时，PDA 状态停止在接收状态
  • acceptance by empty stack: 当输入结束时，PDA 栈空

可以得出这两种方式是等价的，即给定一个语言 ，存在一个 PDA 以 acceptance by final state 的方式定义 ，也存在一个 PDA 以 acceptance by empty stack 的方式定义 。但对于同一个 PDA 而言，以两种方式定义的语言一般是不同的

Acceptance by Final State: 设 PDA ，则 language accepted by by final state 定义为

即在输入结束后，PDA 到达接收状态，而此时栈中可以是任意内容

Acceptance by Empty Stack: 设 PDA ，则 language accepted by by empty stack 定义为

即输入结束后栈清空则视为接受，PDA 此时可以处于任意状态

事实上， 定义的语言集合是相同的，即 CFL。

From Empty Stack to Final State

If for some PDA , then there is a PDA such that

引入一个新的符号 ， 是 的开始符号，其思想在于当 栈中仅有 时，可以得知对于相同的输入， 会清空其栈，即接受该输入。

同样需要引入一个新的开始符号 ，用于将 压入栈中，在此之后 将模拟 的运行，直至栈顶为 ，此时代表 对于同样的输入清空了栈，即接受该输入。引入一个新的状态 用于在栈顶为 且输入结束时转移到该状态。 是 的唯一接受状态

的精确定义为

其中 的定义为

  • ，即开始时 将 压入栈中，同时转移到 的开始状态
  • 对于所有 ，有 ，即 模拟 的运行
  • 对于所有 ，有

只需证明

Proof.

(): 已知 ，则可以在栈底插入符号 ，即

而由于 模拟了所有 的运行，故有

根据 有

即 ，可得

(): 显然，对于 ，其第一步转换必然是 ，因为这是开始状态唯一的转换函数，且若其接受 string，其最后一步转换必然是 ，因为 是唯一的接受状态，且所有输出包含 的转换函数其输入都要求栈中仅有 ，而显然 仅会出现在栈底

这样任意接受 的转换都有如下形式

且除去开始的一步和结尾的一步，中间的转换都是 的转换，且转换过程中 都在栈的底部（ 若出现在栈顶则下一步运行就会结束）。故可将 去掉，得到

即

Q.E.D.

From Final State to Empty State

If for some PDA , then there is a PDA such that

基本思想同样是用 去模拟 的运行，每当 接受输入， 便将栈清空，接受同样的输入。

为了防止在 运行过程中还未接受就将栈清空使得 提前接受，引入新的符号 ，在开始时压入栈，这样无论如何模拟 的运行都不会清空栈，直至其到达接受状态，再将栈中的剩余符号连同 一起弹出

的精确定义为

其中 的定义为

  • ，开始时 将 压入栈中，转到 的开始状态
  • 对于所有 ，有 ，即 模拟 的运行
  • 对于所有 有 ，即当 接受输入时， 开始将自己的栈清空，不再消耗输入
  • 对于所有的 有 ，即当进入状态 后， 将栈中所有的符号弹出直至栈为空，然后接受该输入

只需证明

Proof.

(): 已知 ，显然每一步 的转换都是 的转换，且可以将 插入栈底，故有

则根据 的定义有

于是有

(): 考虑 清空其栈的唯一条件是进入状态 ，因为 在栈底，且 的栈符号集 中没有 。而 进入状态 的条件是 达到某个接受状态 ，而根据 的定义， 的第一个动作一定是

故任意接受 的转换都有如下的形式

而所有 之间的转换都是 的转换，故 也可以有同样的转换，且栈中没有符号 （因为 在栈底且不会被 的转换影响），即

即

Q.E.D.

Equivalence of PDA and CFG

正如 CFG 一样，PDA 定义的语言正好是 CFL（无论是 acceptance by empty stack 还是 acceptance by final state），这说明 PDA 和 CFG 表达能力是等价的

From Grammars to PDA

基本思路为，给出一个 CFG，可以构造一个 PDA 模拟其最左推导过程。而最左推导的每一步是由最左句型来完全表示的。

任何非 terminal string 的最左句型都可以写为 ，其中 是最左的 variable。称 为句型的 tail ，对于一个仅包含 terminal 的最左句型，其 tail 为

使用 PDA 模拟最左推导的思路在于令最左句型 的 tail 出现在栈中，而 是已经消耗的输入，考虑输入字符串 ， 为剩余的输入，则 PDA 的 ID 可以代表最左句型 。假设下一步用于展开 的产生式为 ，则 PDA 的动作是用 替换栈顶的 ，ID 转换为 ，该 PDA 中只有一个状态 ，而现在的 ID 可能不能代表一个最左句型，因为 可能有 terminal 作为前缀，因此需要消耗输入，同时从栈中移除对应的 terminal，直至有一个 variable 出现在了栈顶

若最终成功模拟了最左推导，则所有的 variable 都被展开，所有的 terminal 都与输入中的 symbol 匹配，最终栈为空，接受该输入

令 为 CFG ，则可以构造 PDA ，有

其中 的定义为

对于每个 variable

对于每个 terminal

按照上述方法构造出的 PDA ，有

Proof.

(): 如果 ，则存在一个最左推导序列

则有 ，其中 代表了最左句型 （），其证明基于对 的归纳

Basis. 当 时，有 ，显然有

Induction. 假设 ，由于 是 tail，其第一个 symbol 是某个 variable ，在最左推导 中，使用 的一个产生式 将其展开，而根据 PDA 的构造过程，可以使用 替代栈顶的 ，然后利用输入中的 terminal 将栈中的 terminal 弹出，直到栈顶为下一个 variable，达到 ，即

当 时， ，于是有 ， 接受

(): 需要证明：当 进行一系列操作后，将栈顶的 variable 弹出，同时没有涉及到 以下的栈内容（称其净效应为弹出 ），则 可以推导出在此过程中消耗的所有输入，即

证明将基于 操作的步数

Basis. 只有一步操作，则唯一的可能是 ，则根据 的定义，有 ，即 ，显然

Induction. 考虑 操作了 步，则第一步一定是用 的某个产生式体替换了栈顶的 ，假设用来替换的产生式是

则接下来的 步一定是从输入中消耗了 ，并且其净效应为逐个弹出 ，则可以将 分为 ，其中 代表了从弹出 到弹出 之间消耗的输入（即栈顶从 变为 ），则对于所有 有

由于这其中操作步数都不会超过 ，根据 I. H. 有

于是有推导

即

令 ，由于 ，有 ，则根据上述结论，有 ，即

Q.E.D.

From PDA to Grammars

对任意 PDA 都存在一个 CFG 使得

基本思想是文法中的 variable 代表了 PDA 运行中的一个 event，即 variable 代表了

  • 净效应为从栈中弹出 ，即弹出 的过程不涉及 以下的栈内容
  • 当 从栈中被弹出的同时，状态也从开始的 转换到了

而这个 variable 产生的 string 即是在 event 中被消耗的输入

更为详细的构造为，令 为 PDA ，则构造

其中 包含

  • 特殊的开始符号
  • 其余符号都形如

对于 中的产生式

  • 对所有状态 ， 中有产生式 ，即 产生的 string 可以将 从栈中弹出，同时状态转移到 ，即 。即 将产生所有能让 PDA 清空其栈的 string

  • 若 ，其中 ，则对于任意状态 ，有产生式

    即从栈中弹出 的方法可以是读入 后逐个弹出 ，而期间的状态转换可以是任意状态。若 ，则为

可以证明

Proof.

(): 已知 ，则基于 PDA 的行动数归纳

Basis. 行动一步，则 ，而 为一个 symbol 或是 。根据上述产生式的构造规则，有 ，故

Induction. 考虑操作了 步，则其形式类似

其中

故 ，根据产生式构造规则，有

其中 而其余 可以为任意状态

对任意 ， 是在 被弹出时转换到的状态，可以令 ，其中 为从 弹出到 弹出期间消耗的输入，则有 。由于这些转换都不可能有 步，则根据 I. H. 有

故有

(): 证明基于对推导步数的归纳

Basis. 仅有一步推导，则一定有产生式 ，而根据构造规则，能产生这样的产生式一定说明 ，其中 ，则有

Induction. 考虑 推导用了 步，则其形式形如

其中 ，而产生这样的产生式，根据构造规则，一定说明

则可以将 写作 ，满足 ，由于这些推导步数都不会超过 步，则根据 I. H. 有

由于可以在输入后和栈底添上任意符号串，即

即可得

由于 ，我们得到了

Q.E.D.

则根据上述结论

Deterministic Pushdown Automata

PDA 默认即是 Nondeterministic 的，而实际上 deterministic 的 PDA 也有重要的作用

一个 PDA 是 DPDA (Deterministic PDA) 当且仅当满足

  • 对于任何 ， 只有一个元素
  • 若对 有 非空，则 一定是空的

DPDA 接受的语言集合在正则语言和 CFL 之间，首先可以证明所有的正则语言都可以被 DPDA 接受

如果 是正则语言，则存在 DPDA 使得

Proof.

显然，只需要利用 DPDA 中 DFA 的部分即可

令 DFA ，则可以构造一个 DPDA

对于所有满足 的 ，令 即可

显然 ，证明基于 的长度归纳即可

Q.E.D.

Prefix Property: 在一个 language 中，没有两个不同的字符串满足其中一个是另一个的前缀

则有定理：对某个 DPDA 来说如果语言 当且仅当 有 prefix property 并且存在 DPDA 满足

故可以看出正则语言可以由 acceptance by final state 的 DPDA 描述，但不一定能由 acceptance by empty stack 的 DPDA 描述，即对于 DPDA 来说 的描述能力是强于 的，两者并不等价，事实上， 的描述能力甚至弱于正则，如 虽然 DPDA 能接受形如 这样的非正则的语言，但是也存在 CFL 满足不存在 DPDA 使得 ，如 ，当读完 的时候栈已清空，没有信息用于识别后续的

故对于 DPDA 来说， 识别的语言集合是正则语言的超集，CFL 的子集

如果对 DPDA 有 ，那么这个语言存在一个无歧义的文法

如果对 DPDA 有 ，那么这个语言存在一个无歧义的文法

上述定理的证明可以见课本 P.255-256