O'Reilly logo

Introduction to Formal Languages, Automata Theory and Computation by Kamala Krithivasan, R Rama

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

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

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