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 pqr s ∈ Qt ∈ Γ, and ab ∈ Σε, if δ(pa, ε) contains (rt) and δ(sbt) contains (q, ε), put the rule Apq→ aArsb in G.
  • For each pqr ∈ Q, put the rule Apq→ Apr Arq in G.
  • For each p ∈ Q, put the rule App → ε in G.