ZeePedia

Conversion form of PDA

<< PDA corresponding to CFG
Conversion Form, Joints of the machine >>
img
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
img
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
img
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