Models
for Context-free Languages
Proof: See the previous
algorithm.
Theorem: For every CFG G, there is an PDA M such that L(G) = L(M)e.
Proof: See page 486 in [Meduna:
Automata and Languages]
Theorem: For every PDA M, there is a CFG G such that L(M)e = L(G).
Conclusion: The fundamental models for
context-free languages
are
1) Context-free grammars
2)
Pushdown automata
50/50