Document Type

Open Educational Resource

Publication Date



One of the standard proofs about pushdown automata and context free grammars is that both correspond to the context free languages. The proof is typically in two parts, one showing that for every context free grammar there is a corresponding pushdown automaton, and the other showing that for every pushdown automaton there is a corresponding context free grammar. This resource provides the latter proof for Maheshwari and Smid's pushdown automata.

Creative Commons License

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License. (45 kB)
For adapters, this resource consists of a ZIP archive containing the LaTeX source file for the proof and related image files.