下推自动机与上下文无关文法

上下文无关文法 下推自动机

从上下文无关文法构造下推自动机

设 CFG $G=(V,T,P,S)$，构造 PDA $E=(\{q\},T,V\cup T,\delta ,q,S)$， 其中

• 对每一个 $A\in V$，$\delta (q,ϵ,A)=\{(q,\beta )|A\to \beta \in P\}$
• 对每一个 $a\in T$，$\delta (q,a,a)=\{(q,ϵ)\}$ 则 $N(E)=L(G)$

Proof

即证 $w\in L(G)\iff w\in N(E)$ $\Rightarrow$： 先证若 $A\stackrel{\ast }{\underset{lm}{\Rightarrow }}w$ 则 $(q,w,A){⊢}^{\ast }(q,ϵ,ϵ)$

• 基础：推导步数为 1，则 $A\to w$ 必为产生式，$(q,w,A)⊢(q,w,w){⊢}^{\ast }(q,ϵ,ϵ)$
• 归纳：$(q,w,A)⊢(q,w_1{w}_2\dots w_n,X_1{X}_2\dots X_n){⊢}^{\ast }(q,w_2\dots w_n,X_2\dots X_n){⊢}^{\ast }\cdots {⊢}^{\ast }(q,ϵ,ϵ)$ 因此 $w\in L(G)\Rightarrow w\in N(E)$ $\Leftarrow$： 先证若 $(q,w,A){⊢}^{\ast }(q,ϵ,ϵ)$，则 $A\stackrel{\ast }{\underset{lm}{\Rightarrow }}w$
• 基础：步数为 1，则 $w=ϵ$，$A\to ϵ$ 为产生式，则 $A\underset{lm}{\Rightarrow }w$
• 归纳：设第一步使用产生式 $A\to X_1{X}_2\dots X_m$，将 $w$ 分为 $w_1{w}_2\dots w_m$，$(q,w_i,X_i){⊢}^{\ast }(q,ϵ,ϵ)$ ，无论 $X_i$ 为终结符还是非终结符都有 $X_i\stackrel{\ast }{\underset{lm}{\Rightarrow }}{w}_i$，因此 $A\underset{lm}{\Rightarrow }{X}_1{X}_2\dots X_m\stackrel{\ast }{\underset{lm}{\Rightarrow }}{w}_1{w}_2\dots w_m=w$ 因此 $w\in N(E)\Rightarrow w\in L(G)$

从下推自动机构造等价的上下文无关文法

设 PDA $E=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0),L=N(E)$，构造 CFG $G=(V,\Sigma ,P,S)$，其中

$$V=\{S\}\cup \{[pXq]|p,q\in Q\wedge X\in \Gamma \}$$

产生式 $P$ 定义如下： 对任意 $p\in Q$，$P$ 包含 $S\to [q_0{Z}_{0}p]$ 若 $(q,X_1{X}_2\dots X_k)\in \delta (p,a,X)$，则 $P$ 包含 $[pX{p}_k]\to a[q{X}_1{p}_1][p_1{X}_2{p}_2]\dots [p_{k-1}{X}_k{p}_k]$ 变元 $[pXq]$ 可以理解为当前状态在 $p$，栈顶为 $X$，通过输入，可以将栈顶恰好消去并到达 $q$ 可以证明，此时 $N(E)=L(G)$ 即证存在 $p\in Q,(q_0,w,Z_0){⊢}^{\ast }(p,ϵ,ϵ)\iff S\stackrel{\ast }{\Rightarrow }w$ $\Leftarrow$：由 $G$ 的构造过程，存在 $p$ 满足 $[q_0{Z}_{0}p]\stackrel{\ast }{\Rightarrow }w$ ，从而 $(q_0,w,Z_0){⊢}^{\ast }(p,ϵ,ϵ)$ $\Rightarrow$：先证明对 $p,q\in Q,(q,w,X){⊢}^{\ast }(p,ϵ,ϵ)\iff [qXp]\stackrel{\ast }{\Rightarrow }w$

• 基础：步数为 1，则 $w$ 为 $ϵ$ 或单个符号，$(p,ϵ)\in \delta (q,w,X)$ ，而 $[qXp]\to w$ 是一个产生式。
• 归纳：设第一步推导为 $(q,w,X)⊢(p_0,X_1{X}_2\dots X_k)$，其中 $w=ax$，$a$ 为 $ϵ$ 或单个符号，$(p_0,X_1{X}_2\dots X_k)\in \delta (q,a,X)$，存在 $p_1,p_2,\dots ,p_{k-1}$，满足 $(p_{i-1},x_i,X_i){⊢}^{\ast }(p_i,ϵ,ϵ)$，由构造有 $[qXp]\to a[p_0{X}_1{p}_1]\dots [p_{k-1}{X}_{k}p]$ 为产生式，因此 $[qXp]\stackrel{\ast }{\Rightarrow }w$