Open Educational Resource
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.
Baldwin, Doug, "Pushdown Automata Correspond to Context Free Grammars" (2018). Computability OER. 2.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.