Equivalence of Context-Free Grammars (CFG) and Pushdown Automata (PDA)
Theorem 10
Statement: If a language is context-free, then some pushdown automaton recognizes it.
Proof Overview:
Assume the context-free language ( L ) is generated by a CFG ( G ) in Greibach Normal Form.
Construct a PDA ( M ) using shorthand notation for transition functions to push finite strings onto the stack.
Transition function notation: ( (p, a, A) \rightarrow (q, \gamma) ) means in state ( p ), reading ( a ), and popping ( A ), the PDA pushes ( \gamma ) and transitions to state ( q ).
States of ( M ) include a start state ( q_0 ) and a final state ( q_f ).
( M ) accepts an input string if it can be generated by the grammar.
Lemma 2
Statement: For any PDA ( P ), there exists a PDA ( P' ) such that:
( P' ) has a single accepting state.
( P' ) empties its stack before accepting.
Transitions of ( P' ) either push or pop a symbol, not both.
Proof: To be completed as an exercise.
Lemma 3
Statement: If a language is recognized by a PDA, then it is context-free.
Proof Overview:
Construct a CFG ( G ) from a PDA ( P' ) that meets conditions from Lemma 2.
Variables of ( G ) are derived from states of ( P' ).
Start symbol is ( S ).
Production rules:
For each ( (p, a, q) ), if ( \delta(p, a, A) = (q, \gamma) ), then ( S \rightarrow a ) is a production rule.
For each ( p ), ( S \rightarrow a ) is a production rule.
Claims:
Claim 1: If ( S \Rightarrow^* x ), then ( P' ) can transition from state ( p ) with an empty stack to state ( q ) with an empty stack.
Proved by induction on the number of derivation steps.
Claim 2: If ( P' ) transitions from state ( p ) with an empty stack to state ( q ) with an empty stack, then ( S \Rightarrow^* x ).
Proved by induction on the number of computation steps.
Theorem 11
Statement: A language is context-free if and only if some PDA recognizes it.
Proof:
Follows from Theorem 10 and Lemma 3.
Demonstrates a language is context-free either by constructing a CFG or a PDA.