Equivalence of PDAs and CFGs

We’ll now show that pushdown automata and context-free grammars describe the same class of languages. Just like regular expressions and finite automata, we can construct one from the other in a way that preserves the language in question. One way is trivial, and the other is very involved. We’ll start with the easier way first.

From CFG to PDA

A nondeterministic pushdown automaton can easily simulate the rules of CFG as follows:

1. The PDA has two states: a nonaccepting start state and a second, final state.
2. Place a single transition from the start state to the final state that simply pushes the CFG’s start variable on the stack.
3. For every grammar rule $v\to r$, where $v$ is a variable in the grammar and $r$ is $v$'s replacement, place a self-loop transition on the final state that consumes no input, pops $v$, and pushes $r$—that is, the transition $\lambda,v\to r$.
4. For every terminal symbol, $c$, in the alphabet, $\Sigma$, add a self-loop transition on the final state that reads and pops $c$—that is, the transition $c,c\to \lambda$.

The grammar for the language $L_{eq}=\{w\;|\;w\in (a+b)^* \wedge n_a(w)=n_b(w)\}$, is given as: