Lemma 2.22
If a pushdown automaton recognizes some language, then the language is context-free.
Constructive proof (p. 122)
Let P = (Q, Σ, Γ, δ, q0, {qaccept}). The variables of G are {Ap, q | p, q ∈ Q}. The start variable is Aq0, qaccept. Construct the rules of gramamr G as follows:
- For each p, q, r s ∈ Q, t ∈ Γ, and a, b ∈ Σε, if δ(p, a, ε) contains (r, t) and δ(s, b, t) contains (q, ε), put the rule Apq→ aArsb in G.
- For each p, q, r ∈ Q, put the rule Apq→ Apr Arq in G.
- For each p ∈ Q, put the rule App → ε in G.