T
Chapter 7
Pushdown
Automata
he description of context-free languages by means of context-free
grammars is convenient, as illustrated by the use of BNF in
programming language definition. The next question is whether there
is a class of automata that can be associated with context-free
languages. As we have seen, finite automata cannot recognize all
context-free languages. Intuitively, we understand that this is because finite
automata have strictly finite memories, whereas the recognition of a context-free
language may require storing an unbounded amount of information. For
example, when scanning a string from the language L = {a n b n : n ≥ 0}, we must
not only check that all a’s precede the first b, we must also count the number of
a’s. Since n is unbounded, this counting cannot be done with a finite memory.
We want a machine that can count without limit. But as we see from other
examples, such as {ww R }, we need more than unlimited counting ability: We
need the ability to store and match a sequence of symbols in reverse order. This
suggests that we might try a stack as a storage mechanism, allowing unbounded
storage that is restricted to operating like a stack. This gives us a class of
machines called pushdown automata (pda).
In this chapter, we explore the connection between pushdown automata and
context-free languages. We first show that if we allow pushdown automata to act
nondeterministically, we get a class of automata that accepts exactly the family
of context-free languages. But we will also see that here there is no longer an
equivalence between the deterministic and nondeterministic versions. The class
of deterministic pushdown automata defines a new family of languages, the
deterministic context-free languages, forming a proper subset of the context-free
languages. Since this is an important family for the treatment of programming
languages, we conclude the chapter with a brief introduction to the grammars
Chapter 7
Pushdown
Automata
he description of context-free languages by means of context-free
grammars is convenient, as illustrated by the use of BNF in
programming language definition. The next question is whether there
is a class of automata that can be associated with context-free
languages. As we have seen, finite automata cannot recognize all
context-free languages. Intuitively, we understand that this is because finite
automata have strictly finite memories, whereas the recognition of a context-free
language may require storing an unbounded amount of information. For
example, when scanning a string from the language L = {a n b n : n ≥ 0}, we must
not only check that all a’s precede the first b, we must also count the number of
a’s. Since n is unbounded, this counting cannot be done with a finite memory.
We want a machine that can count without limit. But as we see from other
examples, such as {ww R }, we need more than unlimited counting ability: We
need the ability to store and match a sequence of symbols in reverse order. This
suggests that we might try a stack as a storage mechanism, allowing unbounded
storage that is restricted to operating like a stack. This gives us a class of
machines called pushdown automata (pda).
In this chapter, we explore the connection between pushdown automata and
context-free languages. We first show that if we allow pushdown automata to act
nondeterministically, we get a class of automata that accepts exactly the family
of context-free languages. But we will also see that here there is no longer an
equivalence between the deterministic and nondeterministic versions. The class
of deterministic pushdown automata defines a new family of languages, the
deterministic context-free languages, forming a proper subset of the context-free
languages. Since this is an important family for the treatment of programming
languages, we conclude the chapter with a brief introduction to the grammars