10. PDAs and CFGs

Feb 8-10, 2022

PDA $\iff$ CFG

Prove in two directions:

1. PDA $\subseteq$ CFG

   Convert any context-free grammar $G$ to a PDA $M$ with $L(G)=L(M)$

   Take any arbitrary CFG $G$, conversion procedure:

   • for each production $A\to w$ in $G$, add transition: $ϵ,A\to w$
   • for each terminal $a$ in $G$, add transition: $a,a\to ϵ$

   
   
   Example:

   GRAMMAR                      ε,S → aSTb
   S → aSTb                     ε,S → b
   S → b                        ε,T → Ta
   T → Ta                       ε,T → ε
   T → ε                        a,a → ε
                                b,b → ε
                  ε,ε → S          ⮏        ε,$ → $
    -→ ( q0 ) -----------------> ( q1 ) ---------------------> 《 q2 》
   
   

   In general we can show that grammar $G$ generates string $w$ $S\stackrel{\ast }{\Rightarrow }w$ iff and only if PDA $M$ accepts $w$ $(q_0,w,\mathrm{\$})\stackrel{\ast }{\succ }(q_2,ϵ,\mathrm{\$})$.

   
   

2. PDA $\supseteq$ CFG

   Convert any PDA $M$ to a context-free grammar $G$ with $L(G)=L(M)$

   Take any arbitrary PDA $M$, modify PDA $M$ so that:

   • the PDA has a single accept state
   • use new initial stack symbol # (not used in any transitions)
   • On acceptance the stack contains only stack symbol #
   • Each transition either pushes a symbol or pops a symbol but not both together

   Using this modified PDA, construct the grammar

   Denoting variables: $A_{q_i,q_j}$ where $q_i,q_j$ are states of PDA

   for each state $q$, grammar	$A_{qq}\to ϵ$
   for every 3 states $p,q,r$	$A_{pq}\to A_{pr}{A}_{rq}$
   for every pair of transitions   $p\stackrel{a,ϵ\to t}{⟶}t$     $s\stackrel{b,t\to ϵ}{⟶}q$	$A_{pq}\to a{A}_{rs}b$
   Initial state $q_0$ and accept state $q_f$	Start variable $A_{q_0{q}_f}$

Proving L(G) = L(M)

1. $L(G)\subseteq L(M)$

   We need to show that if $G$ has derivation $A_{q_0{q}_f}\stackrel{\ast }{\Rightarrow }w$ there is an accepting computation in $M$ $(q_0,w,\mathrm{\#})\stackrel{\ast }{\succ }(q_f,ϵ,\mathrm{\#})$ with input string $w$. Will actually show that if $G$ has derivation $A_{pq}\stackrel{\ast }{\Rightarrow }w$, then there is a computation in $M$ $(p,w,ϵ)\stackrel{\ast }{\succ }(q,ϵ,ϵ)$.

   Since there is no transition with # symbol:

   $A_{q_0{q}_f}\stackrel{\ast }{\Rightarrow }w$     =>     $(q_0,w,ϵ)\stackrel{\ast }{\succ }(q_f,ϵ,ϵ)$     =>     $(q_0,w,\mathrm{\#})\stackrel{\ast }{\succ }(q_f,ϵ,\mathrm{\#})$

   If $A_{pq}\stackrel{\ast }{\Rightarrow }w$ (string of terminals) then there is a computation from state $p$ to state $q$ on string $w$ which leaves the stack empty: $(q_0,w,ϵ)\stackrel{\ast }{\succ }(q_f,ϵ,ϵ)$

   Can formally prove this claim by induction on the number of steps in derivation: $A_{pq}\Rightarrow \cdots \Rightarrow w$ where "$\Rightarrow \cdots \Rightarrow$" represents the number of steps.

   
   

   Base case: one derivation step $A_{pq}\Rightarrow w$

   means $A_{qq}\to ϵ$ kind production must have been used, therefore $p=q$ and $w=ϵ$. This computation of PDA trivially exists: $(p,ϵ,ϵ)\stackrel{\ast }{\succ }(p,ϵ,ϵ)$.

   
   

   Inductive step: $k$ derivation steps $A_{pq}\Rightarrow \stackrel{k}{\dots }\Rightarrow w$

   suppose for $k$ steps $(p,w,ϵ)\stackrel{\ast }{\succ }(q,ϵ,ϵ)$ holds. For $k+1$ steps, show that $(p,w,ϵ)\stackrel{\ast }{\succ }(q,ϵ,ϵ)$ holds.

   
   

   case 1:   $A_{pq}\Rightarrow A_{pr}{A}_{rq}\Rightarrow \cdots \Rightarrow w$, we can write $w=yz$ then

       $A_{pq}\Rightarrow \cdots \Rightarrow y$ - at most $k$ steps, and from IH $(p,y,ϵ)\stackrel{\ast }{\succ }(r,ϵ,ϵ)$

       $A_{rq}\Rightarrow \cdots \Rightarrow z$ - at most $k$ steps, and from IH $(r,z,ϵ)\stackrel{\ast }{\succ }(q,ϵ,ϵ)$

       Then $(p,yz,ϵ)\stackrel{\ast }{\succ }(r,z,ϵ)\stackrel{\ast }{\succ }(q,ϵ,ϵ)$, and since $w=yz$, $(p,w,ϵ)\stackrel{\ast }{\succ }(q,ϵ,ϵ)$.

   
   

   case 2:   $A_{pq}\Rightarrow a{A}_{rs}b\Rightarrow \cdots \Rightarrow w$, we can write $w=ayb$

   $A_{pq}\Rightarrow \cdots \Rightarrow y$ at most $k$ steps. From IH, PDA has computation $(r,y,ϵ)\stackrel{\ast }{\succ }(s,ϵ,ϵ)$. Grammar contains production $A_{pq}\Rightarrow a{A}_{rs}b$ and PDA contains transitions:

   • $p\stackrel{a,ϵ\to t}{⟶}t$     =>   $(p,ayb,ϵ)\succ (r,yb,t)$
   • $s\stackrel{b,t\to ϵ}{⟶}q$     =>   $(s,b,t)\succ (q,ϵ,ϵ)$

   We know:   $(r,y,ϵ)\stackrel{\ast }{\succ }(s,ϵ,ϵ)$     =>     $(r,yb,t)\stackrel{\ast }{\succ }(s,b,t)$

   We also know:   $(p,ayb,ϵ)\succ (r,yb,t)$   and   $(s,b,t)\succ (q,ϵ,ϵ)$

   Therefore:   $(p,ayb,ϵ)\succ (r,yb,t)\stackrel{\ast }{\succ }(s,b,t)\succ (q,ϵ,ϵ)$

   Since $w=ayb$,   $(p,w,ϵ)\stackrel{\ast }{\succ }(q,ϵ,ϵ)$.

   
   

2. $L(G)\supseteq L(M)$

   The proof for this direction works the same way as the previous inductive proof.

Therefore $L(G)=L(M)$.