Theory of Automata

<<< Previous Conversion form of PDA Next >>> Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 40
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
B
A
START
ACCEPT
Y
X
PUSH S
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
123 Theory of Automata
(CS402)
becomes
a
b
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
b
becomes
PUSH a
a
b
a
b
POP
PUSH b
\$
b
PUSH \$
To satisfy condition 4,
a
b
POP4
POP5
becomes
a
b
POP4
POP5
HERE
To satisfy condition 5
a
b
POP1
a
124 Theory of Automata
(CS402)
becomes
a
b
POP2
a
a
POP3
To satisfy condition 5
PUSH a
a
a
POP
b
PUSH b
becomes
a
POP1
PUSH a
a