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:

We’ll illustrate the process by creating a PDA for the grammar for the language $L_{eq}$:

This PDA processes a string by applying the transitions corresponding to the rules used in that example. Whenever a symbol of the alphabet is on the top of the stack, there will be a symbol in the input to match if the input string is valid and we have applied the rules correctly, at which point we apply the rule that reads and pops that symbol. The table below processes the string, $baaabb$, from the language $L_{eq}$.

State	Input	Stack	Transition to Apply Next
$q_0$	$baaabb$	$\lambda$	$\lambda,\lambda\to S$
$q_1$	$baaabb$	$S$	$\lambda,S\to SS$
$q_1$

...