基本概念

下推自动机可以理解为在 - NFA 的基础上增加了一个存储“堆栈符号”的堆栈。 下推自动机定义为一个七元组

  • :有穷状态集合
  • :有限输入符号集合
  • :有限栈符号集合,表示可以被压入栈中的符号集合
  • :转移函数。接受一个三元组 ,输出其中
    • 是一个输入符号或空串
    • 是一个栈符号 的输出是一个由 组成的有限集,其中 是新的状态, 是用于改变栈顶符号的栈符号串
  • :初始状态
  • :初始栈符号,有且仅有一个
  • :接受状态集合

Example

接受语言 的 PDA

其中,转移函数为

PDA 的当前格局用三元组 表示,称为 ID, 为当前状态, 为剩余输入串, 是栈中内容。

对任意 ID 对任意 ID ,若 ,则

Theorem

若 ,对任何 有

下推自动机的语言

终态接受的定义

空栈接受的定义

这种情况下终态集合 可以略去。

从空栈接受到终态接受

Theorem

设 PDA ,若 ,则存在 PDA ,使

Proof

新增初始状态 ,作用是将 压入栈中,新增终态 ,对所有 中的状态 ,

Attention

必须在初始状态压入另一初始栈符号,否则在 处于接受状态时,栈已经为空,无法进入终态节点。

从终态接受到空栈接受

Theorem

设 PDA ,若 ,则存在 PDA ,使

Proof

新增初始状态 ,作用是将 压入栈中,新增状态 ,对于所有终态,新增一条到 的转移弧 , 有到自己的转移弧

Attention

必须在初始状态压入另一初始栈符号,否则 会接受 中清空了栈但是没有进入终态的串。

PDA 的设计

例 1

考虑以终态接受的方式构造 PDA。 遇到 a 向栈中压入元素,遇到 b 时弹出元素。为了实现 a 的数量至少 2 倍于 b,应该每次弹出 2 个元素,可以通过引入 实现。

例 2

用 X 对 a 计数,用 Y 对 b 计数,a 遇到 X 则压入 X,遇到 Y 则弹出 Y,b 同理,若串处理完毕,栈中还有元素,则接受。

例 3

每次出现 后必须马上出现 或

例 4

以空栈方式接受 , 只需让 a、b、c 都用 X 计数即可。

例 5

以空栈方式接受 , 用一个状态处理前半段,另一个状态处理后半段,后半段处理时只需判断当前输入是否与栈顶相同即可。

例 6

化简得 或 ,设置两个分支即可

例 7

当且仅当存在前后半段同位置的字符不同,即

以空栈接受

例 8

以终态方式接受 ,用栈量出三分点,保证前三分之一包含

Example

遇到符号 时向栈中压入 3 个元素,遇到符号 时从栈中非确定性地弹出 1-3 个元素。

例 10

转化为 或 或 三类,分别构造

确定型 PDA

一个 PDA 为确定型 PDA 或 DPDA 当且仅当:

  • 对于 或 ,, 至多包含一个元素
  • 对于 ,若 ,则 直观上,如果在任何情况下都不需要移动的选择,则一个 PDA 是确定型的。 有两种类型的选择:
  • 有多个序对
  • 选择用 或

前缀性质

一个语言 L 具有前缀性质,当且仅当不存在 且 为 的前缀。

Theorem

一个语言 是某个 DPDA 的 当且仅当 具有前缀性质且 是某个 DPDA 的

若上下文无关语言 是某个 DPDA 的语言,则称 为一个确定型上下文无关语言。 确定型 PDA 的语言都是上下文无关语言,但确定型 PDA 不能表达所有的 CFL。

Theorem

若 为正规语言,则存在 DPDA ,

忽略 DPDA 的堆栈,可以把它当做一个 DFA

确定型 PDA 与无二义文法

Theorem

一个语言 是一个 DPDA 的 ,则 存在一个无二义文法。

可证由 构造的 CFG 有唯一的最左推导。

Theorem

一个语言 是一个 DPDA 的 ,则 存在一个无二义文法。

记 L'=\{ w\|w\in L }$LL’P’L’=N(P’)G’L=L(G’)G’G$$\to\epsilonL=L(G)$

Theorem

固有二义的语言不是任何 DPDA 的语言

DPDA 的设计

Example

Example

重点是如何避免猜测,转化为第一个 b 出现在串的前三分之一段,即第一个连续的 a 串的长度的三倍小于串的长度

Example

用两个符号记录串 aa 和串 aba 出现的次数,且根据目前哪个串更多分为两种情况: