Algorithm: Grammar2PDA Input: G = (Σ, NT, R, S)
Output: PDA M such that L(M) = L(G)
M = ({q0,q1,q2}, Σ,Σ ∪ NT ∪ {$}, q0, {(q0,λ,λ,q1,$), (q1,λ,S$,q2,λ} ∪ {(q1,λ,w^{R},q1,A) | (A,w) ∈ R} ∪ {(q1,x,λ,q1,x) | x ∈ Σ}, {q2})
It's going to be important in what follows to be able to piece together several computations (given as sequences of configurations) into a single computation (also given as sequences of configurations). The following lemma is the key to doing this.
Lemma 1: For any PDA M, if (p,u,λ) ⇒*_{M} (p',λ,r) and (p',v,λ) ⇒*_{M} (q,λ,t) then (p,uv,λ) ⇒*_{M} (q,λ,tr).Suppose we have (p,aab,λ) ⇒*_{M} (p',λ,Xa) and (p',cbc,λ) ⇒*_{M} (q,λ,bccZ). The theorem tells us that (p,aabcbc,λ) ⇒*_{M} (q,λ,bccZXa).
Lemma 2: Let N be the root node of a sub parse-tree that derives some string u, and let A be the symbol from the grammar that N has as a label. (q1,u,λ) ⇒*_{M} (q1,λ,A)
Suppose the depth is greater than zero. Then node N represents the application of some rule A → w in G, where w ∈ (Σ ∪ {NT})*. If w = λ, then (q1,λ,λ) ⇒_{M} (q1,λ,A). Otherwise, w = w1 w2 ... wk, where the wi are individual symbols, and they are the roots of the individual children of N, N1,N2,...,Nk, respectively. If we use ui to name the string yielded by Ni, then u = u1u2...uk. By induction, for each Ni we have
(q1,ui,λ) ⇒*_{M} (q1,λ,wi).By repeated application of Lemma 1 to
(q1,u1,λ) ⇒*_{M} (q1,λ,w1), (q1,u2,λ) ⇒*_{M} (q1,λ,w2), ... (q1,uk,λ) ⇒*_{M} (q1,λ,wk)we get
(q1,u1u2...uk,λ) ⇒*_{M} (q1,λ,wk...w2w1).Since (q1,λ,wk...w2w1) ⇒_{M} (q1,λ,A), we get that
(q1,u1u2...uk,λ) ⇒*_{M} (q1,λ,A).
Theorem 1: If u ∈ L(G) then w ∈ L(M).
We annotate a configuration by labeling each character on the stack with a sub-parse-tree according to these two rules:
This proof is actually really important, not-only because it's half of showing that M is equivalent to G, but also because it shows that machine M can actually be seen as building a parse tree for the input string. This is, in fact, how tools like bison work.