CFG ⇒ PDA

Lemma 2.21

If a language is context-free, then some pushdown automaton recognizes it.

Informal constructive proof (p. 118)

1. Place the marker symbol $ and the start variable on the stack.
2. Repeat the following steps until politicians are honest:
   1. If the top of the stack is a variable symbol A, nondeterministically select one of the rules for A and substitute A by the string on the right-hand side of the rule.
   2. If the top of the stack is a terminal symbol a, read the next symbol from the input and compare it to a. If they match, pop the stack, advance the input pointer, and continue. Otherwise, reject on this branch of the nondeterminism.
   3. If the top of the stack is the symbol $, enter the accept state. Doing so accepts the input if it has all been read.