CHAPTER 7
PUSHDOWN AUTOMATA
CHAPTER SUMMARY
In the discussion of regular languages, we saw that there were several ways of exploring regular languages: finite automata, regular grammars, and regular expressions. Having defined context-free languages via context-free grammars, we now ask if there are other options for context-free languages. It turns out that there is no analog of regular expressions, but that pushdown automata are the automata associated with context-free languages.
Pushdown automata are essentially finite automata with a stack as storage. Since a stack by definition has infinite length, this overcomes the limitation on finite automata arising from a bounded memory.
Pushdown automata are equivalent to context-free grammars, ...
Get An Introduction to Formal Languages and Automata, 6th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
