**PUSHDOWN AUTOMATA**

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

Start Free Trial

No credit card required