

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 40
Reading
Material
Introduction
to Computer Theory
Chapter
15
Summary
Recap of
example of PDA corresponding to CFG, CFG
corresponding to PDA. Theorem, HERE
state,
Definition
of Conversion form, different
situations of PDA to be converted
into conversion form
Example
Consider
the following CFG
S Æ XY
X Æ aX  bX
a
Y Æ Ya  Yb 
a
First of
all, converting the CFG to
be in CNF, introduce the nonterminals A
and B as
AÆa
BÆb
The
following CFG is in
CNF
S Æ XY
X Æ AX  BX
a
Y Æ YA  YB 
a
AÆa
BÆb
The
PDA corresponding to the above
CFG will be
a
b
a
a
READ3
READ4
READ1
READ2
B
A
START
ACCEPT
Y
X
PUSH
S
READ5
POP
S
Y
X
X
Y
PUSH
X
PUSH
B
PUSH
A
PUSH
X
PUSH
Y
PUSH
X
PUSH
B
PUSH
A
PUSH
Y
PUSH
Y
Theorem
Given a
PDA that accepts the
language L, there exists a
CFG that generates exactly
L.
Before
the CFG corresponding to the
given PDA is determined, the
PDA is converted into the
standard
form
which is
called the conversion
form.
Before
the PDA is converted into
conversion form a new state
HERE is defined which is
placed in the middle
of
any
edge.
Like
READ and POP states,
HERE states are also
numbered e.g.
a
b
READ7
READ9
123
Theory of
Automata
(CS402)
becomes
a
b
READ9
READ7
HERE3
Conversion
form of PDA
Definition
A PDA is
in conversion form if it fulfills
the following conditions:
There is
only one ACCEPT
state.
There
are no REJECT states.
Every
READ or HERE is followed immediately by a
POP i.e.
every
edge leading out of any READ
or HERE
state
goes directly into a POP
state.
No two
POPs exist in a row on the
same path without a READ or
HERE between them whether or not
there are
any
intervening PUSH states (i.e.
the
POP states must be separated
by READs or HEREs).
All
branching, deterministic or nondeterministic occurs at
READ or HERE states, none at
POP states and
every
edge
has only one label.
Even
before we get to START, a
"bottom of STACK" symbol $ is
placed on the STACK. If this
symbol is ever
popped in
the processing it must be
replaced immediately. The STACK is
never popped beneath this
symbol.
Right
before entering ACCEPT this symbol is
popped out and left.
The
PDA must begin with the
sequence
$
START
POP
PUSH
$
HERE
The
entire input string must be read
before the machine can
accept the word.
Different
situations of a PDA to be converted
into conversion
form are
discussed as follows
To
satisfy condition 3,
a
b
READ7
READ8
b
becomes
PUSH
a
a
b
a
b
READ7
POP
READ7
PUSH
b
$
b
PUSH
$
To
satisfy condition 4,
a
b
POP4
POP5
becomes
a
b
POP4
POP5
HERE
To
satisfy condition 5
a
b
READ2
READ1
POP1
a
READ3
124
Theory of
Automata
(CS402)
becomes
a
b
READ1
READ2
POP2
a
a
READ3
POP3
To
satisfy condition 5
PUSH
a
a
a
READ1
READ2
POP
b
PUSH
b
becomes
a
POP1
PUSH
a
a
READ1
READ2
a
b
POP2
PUSH
b
To
satisfy condition 6, it is supposed
that the STACK is initially
in the position shown below
STACK
$
D
125
Table of Contents:

