ZeePedia

Nondeterministic PDA

<< A new format for FAs
PDA corresponding to CFG >>
img
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 Non-Derterministic PDA, Definition of PUSH DOWN Automata, Example of
Non-Derterministic 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
img
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 EVEN-EVEN language
a
±
a
b
b
b
b
a
a
The corresponding PDA will be
115
img
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
img
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 out-edge and no in-edge.
Two halt states i.e. ACCEPT and REJECT states, with in-edges and no out-edges.
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 out-edges with same label).
A READ state that reads the next unused letter from the TAPE, (may contain more than one out-edges with
same label).
Example: Consider the CFG
S Æ S+S|S*S|4
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
img
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