Pushdown Automata
In this chapter we introduce pushdown automaton (pda). We discuss two types
of acceptance of sets by pushdown automata. Finally, we prove that the sets
accepted by pushdown automata are precisely the class of context-free
languages.
7.1 BASIC DEFINITIONS
We have seen that the regular languages are precisely those accepted by finite
automata. If M is a finite automaton accepting L, it is constructed in such a way
that states act as a form of primitive memory. The states 'remember' the
variables encountered in the course of derivation of a string. (In M, the states
correspond to variables.) Let us consider L = {a"b"ln ~ I}. This is a contextfree language but not regular. (S -----i aSh Iab generates L. Using the pumping
lemma we can show that L is not regular; cf. Example 5.20.)
A finite automaton cannot accept L, i.e. strings of the form a"b", as it has
to remember the number of a's in a string and so it will require an infinite
number of states. This difficulty can be avoided by adding an auxiliary
memory in the form of a 'stack' (In a stack we add the elements in a linear
way. While removing the elements we follow the last-in-first-out (LIFO)
basis. i.e. the most recently added element is removed first.) The a's in the
given string are added to the stack. When the symbol b is encountered in the
input string, an a is removed from the stack. Thus the matching of number
of c's and the number of b's is accomplished. This type of arrangement where
a finite automaton has a stack leads to the generation of a pushdown
automaton.
Before giving the rigorous definition, let us consider the components of a
pushdown automaton and the way it operates. It has a read-only input tape,
227
In this chapter we introduce pushdown automaton (pda). We discuss two types
of acceptance of sets by pushdown automata. Finally, we prove that the sets
accepted by pushdown automata are precisely the class of context-free
languages.
7.1 BASIC DEFINITIONS
We have seen that the regular languages are precisely those accepted by finite
automata. If M is a finite automaton accepting L, it is constructed in such a way
that states act as a form of primitive memory. The states 'remember' the
variables encountered in the course of derivation of a string. (In M, the states
correspond to variables.) Let us consider L = {a"b"ln ~ I}. This is a contextfree language but not regular. (S -----i aSh Iab generates L. Using the pumping
lemma we can show that L is not regular; cf. Example 5.20.)
A finite automaton cannot accept L, i.e. strings of the form a"b", as it has
to remember the number of a's in a string and so it will require an infinite
number of states. This difficulty can be avoided by adding an auxiliary
memory in the form of a 'stack' (In a stack we add the elements in a linear
way. While removing the elements we follow the last-in-first-out (LIFO)
basis. i.e. the most recently added element is removed first.) The a's in the
given string are added to the stack. When the symbol b is encountered in the
input string, an a is removed from the stack. Thus the matching of number
of c's and the number of b's is accomplished. This type of arrangement where
a finite automaton has a stack leads to the generation of a pushdown
automaton.
Before giving the rigorous definition, let us consider the components of a
pushdown automaton and the way it operates. It has a read-only input tape,
227