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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.