O'Reilly logo

An Introduction to Formal Languages and Automata, 6th Edition by Linz

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required