 |
Nondeterministic PDA |
| << A new format for FAs |
| PDA corresponding to CFG >> |
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
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
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 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
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:
- What does automata mean, Introduction to languages
- Kleene Star Closure, Recursive definition of languages
- Regular Expression, Recursive definition of Regular Expression
- Equivalent Regular Expressions
- Finite Automaton
- Equivalent FAs
- FA corresponding to finite languages
- Examples of TGs: accepting all strings
- Generalized Transition Graphs
- Nondeterminism, Kleene’s Theorem
- Proof(Kleene’s Theorem Part II)
- Kleene’s Theorem Part III
- Concatenation of FAs
- Closure of an FA
- Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA
- NFA with Null String
- NFA and Kleene’s Theorem
- NFA corresponding to Concatenation of FAs
- Distinguishable strings and Indistinguishable strings
- Finite Automaton with output, Moore machine
- Mealy machine
- Equivalent machines
- Mealy machines in terms of sequential circuit
- Regular languages, Complement of a language
- Nonregular languages
- Pumping Lemma
- Pumping Lemma version II
- Pseudo theorem
- Decidability
- finiteness of a language
- Context Free Grammar (CFG), CFG terminologies
- Trees
- Polish Notation (o-o-o)
- Total language tree, Regular Grammar
- Null Production
- Chomsky Normal Form (CNF)
- A new format for FAs
- Nondeterministic PDA
- PDA corresponding to CFG
- Conversion form of PDA
- Conversion Form, Joints of the machine
- Row language, Nonterminals
- Non-Context-Free language, Pumping lemma for CFLs
- Decidablity, Parsing Techniques
- Turing machine