Equivalence of PDAs and CFGs

Learn how to convert a context-free grammar to a PDA and a special case of conversion of a PDA to a CFG.

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 vrv\to r, where vv is a variable in the grammar and rr is vv's replacement, place a self-loop transition on the final state that consumes no input, pops vv, and pushes rr—that is, the transition λ,vr\lambda,v\to r.
  4. For every terminal symbol, cc, in the alphabet, Σ\Sigma, add a self-loop transition on the final state that reads and pops cc—that is, the transition c,cλc,c\to \lambda.

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

Get hands-on with 1200+ tech skills courses.