ZeePedia

PDA corresponding to CFG

<< Nondeterministic PDA
Conversion form of PDA >>
img
Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 39
Reading Material
Introduction to Computer Theory
Chapter 15
Summary
PDA corresponding to CFG, Examples of PDA corresponding to CFG
PDA corresponding to CFG
Theorem
Corresponding to any CFG there exists a PDA accepting the language generated by the CFG.
Since an algorithm has already been discussed to convert the CFG in CNF, so the PDA can be constructed
corresponding to the CFG. As the CFG in CNF generates all the nonnull words of the corresponding CFL, so
accepting the null string (if it is contained in the CFL), can be managed separately.
Example
Consider the following CFG which is in CNF and does not generate the null string
S Æ SB|AB
A Æ CC
BÆb
CÆa
The corresponding PDA will be
a
b
READ1
READ2
ACCEPT
START
C
B
READ3
PUSH S
POP
S
A
S
PUSH C
PUSH B
PUSH B
PUSH S
PUSH A
PUSH C
Here the STACK alphabet G= {S, A, B, C}, where the TAPE alphabet Â={a, b}
Note: It may be noted that when the POP state is entered either a nonterminal is replaced by two nonterminals at
the top of the STACK accommodating a production, or a nonterminal is popped out from the top of the stack
and a READ state is entered to read a specified letter from the TAPE or else the machine crashes.
The choice of path taken at POP state to accommodate the word belonging to the CFL can be determined by the
left most derivation of the word. Consider the word aab with its left most derivation, as follows
119
img
Theory of Automata
(CS402)
Working-String Generation
Production
Used
S fi AB
S Æ AB
step 1
fi CCB
A Æ CC
step 2
fi aCB
CÆa
step 3
fi aaB
CÆa
step 4
fi aab
BÆb
step 5
First of all the START state is entered
STACK
TAPE
...
aab ...
The PUSH S state is entered
STACK
TAPE
aab ...
S
The POP state is entered and to accommodate the production S Æ AB, PUSH B and PUSH A states are entered.
STACK
TAPE
aab ...
AB
Then the POP state is entered and to accommodate the production A Æ CC, PUSH C, PUSH C states are entered
STACK
TAPE
CCB
aab
The POP state is entered and to accommodate the production C Æ a, READ1 is entered and the letter a is read
from the TAPE.
STACK
TAPE
CB
aab
The POP state is entered and to accommodate the production C Æ a, READ1 state is entered and the letter a is
read from the TAPE
STACK
TAPE
aab
B
The POP state is entered and to accommodate the production B Æ b, READ2 state is entered and the letter b is
read from the TAPE
STACK
TAPE
aab
D
The D shown in the STACK indicates that there are no nonterminals in the working string and D is read from the
STACK which leads to READ3 state where the D is read from the TAPE and the ACCEPT state is entered
which shows that the word aab is accepted by the PDA.
Following is the table showing all the observations discussed above, for the word aab
120
img
Theory of Automata
(CS402)
Left most
STATE
STACK
TAPE
derivation
D
START
aab
S
PUSH S
S
aab
D
POP
aab
aab
PUSH B
B
fiAB
PUSH A
AB
aab
POP
B
aab
PUSH C
CB
aab
fiCCB
PUSH C
CCB
aab
POP
CB
aab
fiaCB
READ1
CB
aab
POP
B
aab
fiaaB
READ1
B
aab
D
POP
aab
fiaab
D
READ2
aab
D
POP
aab
D
READ3
aab
D
ACCEPT
aab
Following is an example of building the PDA corresponding to the given CFG
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
121
img
Theory of Automata
(CS402)
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 B
PUSH X
PUSH A
PUSH X
PUSH Y
PUSH X
PUSH B
PUSH A
PUSH Y
PUSH Y
The word aaab can be generated as
Working-String Generation
Production
Used
S fi XY
S Æ XY
step 1
fi AXY
X Æ AX
step 2
fi aXY
AÆa
step 3
fi aaY
XÆa
step 4
fi aaYB
Y Æ YB
step 5
fi aaaB
YÆa
step 6
fi aaab
BÆb
step 7
STACK
TAPE
STACK
TAPE
(START)
aaab
(POP)
Y
aaab
(PUSH S) S
aaab
(READ1) Y
aaab
(POP)
(POP)
aaab
aabb
(PUSH Y) Y
aaab
(PUSH B) B
aabb
(PUSH X) XY
aaab
(PUSH Y) YB
aabb
aaab
(POP)
Y
aaab
(POP)
B
(PUSH X) XY
aaab
(READ2) B
aaab
(POP)
(PUSH A) AXY
aaab
aaab
(POP) XY
aaab
(READ4)
aaab
(POP)
(READ3) XY
aaab
122