

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 38
Reading
Material
Introduction
to Computer Theory
Chapter
14
Summary
Example
of PDA with table for
running a string, Equivalent PDA,
PDA for EVEN EVEN
Language. Non
Derterministic
PDA, Example of NonDerterministic
PDA, Definition of PUSH DOWN
Automata, Example of
NonDerterministic
PDA.
START
a
READ1
PUSH
a
b
b
a
POP2
POP1
READ2
a,b
b,
a
REJECT
ACCEPT
REJECT
Note
The
process of running the string
aaabbb can also be expressed
in the following
table
STATE
STACK
TAPE
START
...
aaabbb
...
READ1
...
aaabbb
...
PUSH
a
a...
aaabbb
...
READ1
a...
aaabbb
...
PUSH
a
aa
...
aaabbb
...
READ1
aa
...
aaabbb
...
PUSH
a
aaa
...
aaabbb
...
READ1
aaa
...
aaabbb
...
POP1
aa
...
aaabbb
...
114
Theory of
Automata
(CS402)
STATE
STACK
TAPE
aaabbb
...
aa
...
READ2
POP1
a...
aaabbb
...
READ2
a...
aaabbb
...
POP1
...
aaabbb
...
READ2
...
aaabbb
...
POP2
...
aaabbb
...
ACCEPT
...
aaabbb
...
It may be
observed that the above PDA
accepts the language {anbn :
n=0,1,2,3, ...}.
Note
It may be
noted that the TAPE
alphabet Σ and STACK
alphabet G, may be
different in general and hence
the
PDA
equivalent to that accepting
{anbn:
n=0,1,2,3...} discussed above
may be
START
a
READ1
PUSH
X
b
b
X
X
POP2
POP1
READ2
a
REJECT
ACCEPT
Following
is an example of PDA corresponding to an
FA
Example
Consider
the following FA corresponding to the
EVENEVEN language
a
±
a
b
b
b
b
a
a
The
corresponding PDA will be
115
Theory of
Automata
(CS402)
REJECT
ACCEPT
a
D
D
START
READ1
READ2
a
b
b
b
b
a
READ3
READ4
D
a
D
REJECT
REJECT
Nondeterministic
PDA
Like TGs
and NFAs, if in a PDA there
are more than one outgoing
edges at READ or POP states
with one label,
then it
creates nondeterminism and the
PDA is called nondeterministic
PDA.
In nondeterministic
PDA no edge is labeled by string of terminals or
nonterminals, like that can be observed
in
TGs. Also
if there is no edge for any
letter to be read from the
TAPE, the machine crashes
and the string is
rejected.
In nondeterministic
PDA a string may trace more
than one paths. If there
exists at least one path
traced by a
string leading to
ACCEPT state, then the
string is supposed to be accepted, otherwise
rejected.
Following
is an example of nondeterministic
PDA
a
START
POP1
a
a
b
a
b
PUSH
a
READ1
b
READ2
POP2
b
PUSH
b
POP3
Here the
nondeterminism can be observed at state
READ1ACCEPT observed
that the above PDA
accepts the
. It can
be
language
EVENPALINDROME={w
reverse(w): wOE{a,
b}*}
={L, aa,
bb, aaaa, abba, baab,
bbbb, ...}
Now
the definition of PDA
including the possibility of
nondeterminism may be given as
follows
PUSHDOWN
AUTOMATON (PDA)
Pushdown
Automaton (PDA), consists of the
following
116
Theory of
Automata
(CS402)
An
alphabet S of input
letters.
An input
TAPE with infinite many
locations in one direction. Initially
the input string is placed in it
starting
from
first cell, the remaining part of
the TAPE is empty.
An
alphabet G of STACK
characters.
A pushdown
STACK which is initially
empty, with infinite many
locations in one direction. Initially
the
STACK
contains blanks.
One
START state with only
one outedge and no
inedge.
Two halt
states i.e.
ACCEPT
and REJECT states, with
inedges and no
outedges.
A PUSH
state that introduces
characters onto the top of the
STACK.
A POP
state that reads the top
character of the STACK, (may contain more
than one outedges with
same label).
A READ
state that reads the
next unused letter from the
TAPE, (may contain more than one
outedges with
same
label).
Example:
Consider the CFG
S Ć S+SS*S4
Following
is the PDA accepting the
corresponding CFL
*
4
+
READ3
READ1
READ2
ACCEPT
START
+
*
S
PUSH1 S
READ4
POP
S
S
PUSH5 S
PUSH2 S
PUSH6 *
PUSH3 +
PUSH4 S
PUSH7 S
The
string 4 + 4 * 4 traces the path shown in
the following table
STATE
STACK
TAPE
START
4+4*4
PUSH1 S
S
4+4*4
POP
4+4*4
PUSH2 S
S
4+4*4
PUSH3 +
+S
4+4*4
PUSH4 S
S+S
4+4*4
POP
+S
4+4*4
READ1
+S
+4*4
POP
S
+4*4
117
Theory of
Automata
(CS402)
STATE
STACK
TAPE
READ2
S
4*4
POP
4*4
PUSH5 S
S
4*4
PUSH6 *
*S
4*4
PUSH7 S
S*S
4*4
POP
*S
4*4
READ1
*S
*4
POP
S
*4
READ3
S
4
POP
4
READ1
POP
READ4
ACCEPT
Note
It may be
noted that the letters
are deleted from the
TAPE instead of underlined.
It may
also be noted that the
choice of path at POP state
can be determined by the left
most deviation of the
string
belonging to the CFL.
118
Table of Contents:

