下推自动机

基本概念

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

$$P=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$$

• $Q$：有穷状态集合
• $\Sigma$：有限输入符号集合
• $\Gamma$：有限栈符号集合，表示可以被压入栈中的符号集合
• $\delta$：转移函数。接受一个三元组 $(q,a,X)$，输出其中
  • $q\in Q$
  • $a\in (\Sigma \cup \{ϵ\})$ 是一个输入符号或空串
  • $X\in \Gamma$ 是一个栈符号 $\delta$ 的输出是一个由 $(p,r)$ 组成的有限集，其中 $p\in Q$ 是新的状态，$\gamma \in {\Gamma }^{\ast }$ 是用于改变栈顶符号的栈符号串
• $q_0$：初始状态
• $Z_0$：初始栈符号，有且仅有一个
• $F$：接受状态集合

Example

接受语言 $L=\{0^n{1}^n|n\ge 1\}$ 的 PDA

$P=(\{q_0,q_1,q_2\},\{0,1\},\{X,Z_0\},\delta ,q_0,Z_0,\{q_2\})$ 其中，转移函数为

$$\delta (q_0,0,Z_0)=\{(q_0,X{Z}_0)\},\delta (q_0,0,X)=\{(q_0,XX)\},$$ $$\delta (q_0,1,X)=\{(q_1,ϵ)\},\delta (q_1,1,X)=\{(q_1,ϵ)\}$$ $$\delta (q_1,ϵ,Z_0)=\{(q_2,Z_0)\}$$

PDA 的当前格局用三元组 $(q,w,\gamma )$ 表示，称为 ID，$q$ 为当前状态，$w$ 为剩余输入串，$\gamma$ 是栈中内容。

$$(q,aw,X\beta )⊢(p,w,\alpha \beta )\iff (p,\alpha )\in \delta (q,a,X)$$

对任意 ID $I,I{⊢}^{\ast }I$ 对任意 ID $I,J,K$，若 $I⊢K,K{⊢}^{\ast }J$，则 $I{⊢}^{\ast }J$

Theorem

若 $q,x,\alpha {⊢}^{\ast }(p,y,\beta )$,对任何 $w\in {\Sigma }^{\ast },\gamma \in {\Gamma }^{\ast }$ 有 $(q,xw,\alpha \gamma ){⊢}^{\ast }(p,yw,\beta \gamma )$

下推自动机的语言

终态接受的定义

$L(P)=\{w|(q_0,w,Z_0){⊢}^{\ast }(q,ϵ,\alpha ),q\in F,\alpha \in {\Gamma }^{\ast }\}$

空栈接受的定义

$N(P)=\{w|(q_0,w,Z_0){⊢}^{\ast }(q,ϵ,ϵ),q\in Q\}$ 这种情况下终态集合 $F$ 可以略去。

从空栈接受到终态接受

Theorem

设 PDA $P_N$，若 $L=N(P_N)$，则存在 PDA $P_F$，使 $L=L(P_F)$

Proof

新增初始状态 $p_0$，作用是将 $X_0$ 压入栈中，新增终态 $p_f$，对所有 $P_N$ 中的状态 $q$，${\delta }_F(q,ϵ,X_0)=\{(p_f,ϵ)\}$

Attention

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

从终态接受到空栈接受

Theorem

设 PDA $P_F$，若 $L=L(P_N)$，则存在 PDA $P_N$，使 $L=N(P_N)$

Proof

新增初始状态 $p_0$，作用是将 $X_0$ 压入栈中，新增状态 $p$，对于所有终态，新增一条到 $p$ 的转移弧 $(ϵ,any/ϵ)$，$p$ 有到自己的转移弧 $(ϵ,any/ϵ)$

Attention

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

PDA 的设计

例 1

$L=\{w\in \{a,b{\}}^{\ast }|w中任何前缀中a的数量至少2倍于b的数量\}$

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

例 2

$L=\{w\in \{a,b{\}}^{\ast }|w中a的数量不等于b的数量\}$

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

例 3

$L=\{w\in \{a,b,c{\}}^{\ast }|w中a和b的个数相等且不含连续的c\}$

每次出现 $c$ 后必须马上出现 $a$ 或 $b$

例 4

$L=\{a^n{b}^m{c}^k|n,m,k\ge 0且n+2m=k\}$

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

例 5

$L=\{w{w}^R|w\in \{a,b{\}}^{\ast }\}$

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

例 6

$L=\{a^n{b}^m{c}^k|n,m,k\ge 0且n^2+mk=nm+nk\}$

化简得 $n=m$ 或 $n=k$，设置两个分支即可

例 7

$L=\{uv|u,v\in \{a,b{\}}^{\ast },|u|=|v|且u\ne v\}$

$w\in L$ 当且仅当存在前后半段同位置的字符不同，即

$$w=(a+b{)}^{m}x(a+b{)}^n(a+b{)}^{m}y(a+b{)}^n=(a+b{)}^{m}x(a+b{)}^{m+n}y(a+b{)}^n$$

以空栈接受 $L$

例 8

$L=\{w\in \{a,b{\}}^{\ast }||w|为3的倍数，且w前三分之一段不属于L(a^{\ast })\}$

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

Example

$L=\{a^i{b}^i|0\le i\le j\le 3i\}$

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

例 10

$L=\{a^i{b}^j|i,j>0,i\ne j且2i\ne j\}$

转化为 $j<i$ 或 $i<j<2i$ 或 $2i<j$ 三类，分别构造

确定型 PDA

一个 PDA $P=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$ 为确定型 PDA 或 DPDA 当且仅当：

• 对于 $a\in \Sigma$ 或 $a=ϵ$，$X\in \Gamma$，$\delta (q,a,X)$ 至多包含一个元素
• 对于 $a\in \Sigma$，若 $\delta (q,a,X)\ne \varnothing$，则 $\delta (q,ϵ,X)=\varnothing$ 直观上，如果在任何情况下都不需要移动的选择，则一个 PDA 是确定型的。 有两种类型的选择：
• $\delta (q,a,X)$ 有多个序对
• 选择用 $a\ne ϵ$ 或 $ϵ$

前缀性质

一个语言 L 具有前缀性质，当且仅当不存在 $x,y\in L,x\ne y$ 且 $x$ 为 $y$ 的前缀。

Theorem

一个语言 $L$ 是某个 DPDA $P$ 的 $N(P)$ 当且仅当 $L$ 具有前缀性质且 $L$ 是某个 DPDA $P^{\prime }$ 的 $L(P^{\prime })$

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

Theorem

若 $L$ 为正规语言，则存在 DPDA $P$，$L(P)=L$

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

确定型 PDA 与无二义文法

Theorem

一个语言 $L$ 是一个 DPDA $P$ 的 $N(P)$，则 $L$ 存在一个无二义文法。

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

Theorem

一个语言 $L$ 是一个 DPDA $P$ 的 $L(P)$，则 $L$ 存在一个无二义文法。

记 L'=\{ w\|w\in L }$，其中$$$不出现在$L$的任何串中，$L’$具有前缀性质，因此存在DPDA$P’$使得$L’=N(P’)$，因此存在一个无二义文法$G’$，$L=L(G’)$，从$G’$构造$G$，将$$$视为非终结符，增加产生式$$\to\epsilon$，得$L=L(G)$

Theorem

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

DPDA 的设计

Example

$\{0^n{1}^{n+2}|n\ge 0\}$

Example

$L=\{w\in \{a,b{\}}^{\ast }||w|为3的倍数，且w的前三分之一不属于L(a^{\ast })\}$ 重点是如何避免猜测，转化为第一个 b 出现在串的前三分之一段，即第一个连续的 a 串的长度的三倍小于串的长度

Example

$L=\{w\in \{a,b{\}}^{\ast }|w中串aa出现的次数不少于串aba出现的次数\}$ 用两个符号记录串 aa 和串 aba 出现的次数，且根据目前哪个串更多分为两种情况：