Chapter 7. Pushdown Automata
In the earlier chapters, we have considered the simplest type of automaton, namely, the FSA. We have seen that a FSA has finite amount memory and hence cannot accept type 2 languages like {anbn|n ≥ 1}. In this chapter, we consider a class of automata, the pushdown automata, which accept exactly the class of context-free (type 2) languages. The pushdown automaton is a finite automaton with an additional tape, which behaves like a stack. We consider two ways of acceptance and show the equivalence between them. The equivalence between context-free grammars (CFG) and pushdown automata is also proved.
The Pushdown Automaton
Let us consider the following language over the alphabet Σ = {a, b, c}: L = {anbmcn|n, m ≥ 1}. To accept ...
Get Introduction to Formal Languages, Automata Theory and Computation 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.
