Chap ter 3
Pushdown Autom ata
3.1 DEFINITIONS
Let us consider a finite automata which accepts the language
L M
a b m n
m n
1
1
( ) {
| ,
}.
=
≥
We see that M moves from q 0 to q 1 , on the occurence of a’s. On seeing ‘b’,
M moves from q 1 to q 2 and continues to be in the state q 2 on getting more b’s.
Assume that the input string is given by
a b
m n ,
then the resulting state is final state and so M accepts a b
m n .
Consider the language L M
a b n
n n
2
1
( ) {
|
}
=
≥ where the number of b’s
and a’s are equal. The FA constructed for L 1 differs from that of L 2 .
For the language L M
a b m n
m n
1
1
( ) {
| ,
}
=
≥ there is not necessity to
remember the number of a’s. The following have to be remembered.
(a) Whether the first symbol is ‘b’ (to reject the string)
(b) Whether ‘a’ follows ‘b’ (to reject the string)
(c) Whether ‘a’ follows ‘a’ and ‘b’ follows ‘b’ (to accept the string).
We know that FA has only a finite number of states, M cannot remember
the number of a’s in a
n b
n where ‘n’ is larger than the number of states of M.
The FA does not accept the sets of the form {
|
}.
a b n
n n
≥1 This is taken
care by a “PUSHDOWN AUTOMATA”.
Let us illustrate a Pushdown Automata (PDA) model.
3.1.1 Nondeterministic PDA (Def i ni tion)
An NPDA is defined by the 7-tuple
M
Q
q Z F
= ( , , , , , , )
Σ Γ δ 0
where
Q = Finite set of inter nal states of the con trol unit
Σ = Input alpha bet
Γ = Finite set of sym bols called “Stack alpha bet”