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:
- The PDA has two states: a nonaccepting start state and a second, final state.
- Place a single transition from the start state to the final state that simply pushes the CFG’s start variable on the stack.
- For every grammar rule , where is a variable in the grammar and is 's replacement, place a self-loop transition on the final state that consumes no input, pops , and pushes —that is, the transition .
- For every terminal symbol, , in the alphabet, , add a self-loop transition on the final state that reads and pops —that is, the transition .
The grammar for the language , is given as:
Get hands-on with 1200+ tech skills courses.