Pushdown Automata Correspond to Context Free Grammars

Authors

Doug Baldwin, SUNY GeneseoFollow

Document Type

Open Educational Resource (OER)

Publication Date

5-2018

Abstract

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.

Recommended Citation

Baldwin, Doug, "Pushdown Automata Correspond to Context Free Grammars" (2018). Computability OER. 2.
https://knightscholar.geneseo.edu/computability-oer/2

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 License.