Lec 19 : Computation Theory Equivalence of PDAs and CFGs
1
Equivalence of PDAs and CFGs
A language is context iff some PDA recognize it
If L=L(G) for some CFG G, then L=L(M) for some PDA M.
Proof idea
* Need to show that given CFG G, we can find PDA M that
recognize the same language
G generates.
* Basic idea is to build PDA that simulates a leftmost derivation.
* For example, consider CFG G=(V,?,R,S)
Variables V= {S}
Terminales ?={0,1}
Rules R= S?0S0S| 1S0| 1
* Leftmost derivation of string 010110 ? L(G)
S?0S0S?010S?0101S0?010110
Creat PDA for CFG as follow:
* PDA works as follow:
1- push S on the stack, where S is start variable.
2- Repeat following until stack empty
q 0
q0
q1
?,Z\SZ q2
?,A\u, ? rules A?u
a,a\?, ? terminals a? ?
?,Z\Z
Lec 19 : Computation Theory Equivalence of PDAs and CFGs
2
(a) if top of stack is variable A?V, then replace A by some
u?(??V)*, where A?u is a rule in R.
(b) if top of stack is terminal a?? and current input symbol is a,
then pop.
(c) if top of stack is Z, then accept.
Recall CFG S?0S0S0| 1S0| 1
Corresponding PDA
* PDA is non-deterministic
* Input alphabet of PDA is the terminal of CFG ?={0,1}
* Stack alphabet of PDA consists of all variables, terminals and
Z ? ={S,0,1,Z}
* PDA simulates a leftmost derivation using CFG
Let’s now process string 010110 on PDA
0- start in state q0 with 010110 on input tape and empty stack
q 0
q0
q1
?,Z\SZ q2
?,S\?,0S0S
?,S\?,1S
?,S\?,1
1,1\?
0,0\?
?,Z\Z
Lec 19 : Computation Theory Equivalence of PDAs and CFGs
3
1- read nothing, pop nothing, push S and move to q1
q 0
q0
q1
q2
?,Z\SZ
?,S\?,0S0S
?,S\?,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
S
Z0
Stack
q 0
q0
q1 q2 ?,Z\SZ
?,S\?,0S0S
?,S\?,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
Z0
Stack
Lec 19 : Computation Theory Equivalence of PDAs and CFGs
4
2- read nothing, pop S , push 0S0S, and return to q1
3- read 0,pop 0, push nothing, and return to q1
q 0
q0
q1 q2 ?,Z\SZ
?,S\? ,0S0S
?,S\?,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
0
S
0
S
Z0
Stack
q 0
q0
q1
?,Z\SZ q2
?,S\?,0S0S
?,S\?,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
S
0
S
Z0
Stack
Lec 19 : Computation Theory Equivalence of PDAs and CFGs
5
4- read nothing, pop S, push 1, and return to q1
5- read 1, pop 1, push nothing and return to q1
q 0
q0
q1 q2 ?,Z\SZ
?,S\?,0S0S
?,S\?,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
1
0
S
Z0
Stack
q 0
q0
q1 q2 ?,Z\SZ
?,S\?,0S0S
?,S\?,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
0
S
Z0
Stack
Lec 19 : Computation Theory Equivalence of PDAs and CFGs
6
6- read 0, pop 0, push nothing, and return to q1
7- read nothing, pop S, push 1S0, and return to q1
q 0
q0
q1 q2 ?,Z\SZ
?,S\?,0S0S
?,S\?,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
S
Z0
Stack
q 0
q0
q1
?,Z\SZ q2
?,S\?,0S0S
?,S\? ,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
1
S
0
Z0
Stack
Lec 19 : Computation Theory Equivalence of PDAs and CFGs
7
8- read 1, pop1, push nothing, and return to q1
9- read nothing, pop S, push 1, and return to q1
q 0
q0
q1
?,Z\SZ q2
?,S\?,0S0S
?,S\?,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
S
0
Z0
Stack
q 0
q0
q1
?,Z\SZ q2
?,S\?,0S0S
?,S\?,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
1
0
Z0
Stack
Lec 19 : Computation Theory Equivalence of PDAs and CFGs
8
10- read 1, pop1, push nothing, and return to q1
11- read 0, pop0, push nothing, and return to q1
q 0
q0
q1 q2 ?,Z\SZ
?,S\?,0S0S
?,S\?,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
0
Z0
Stack
q 0
q0
q1 q2 ?,Z\SZ
?,S\?,0S0S
?,S\?,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
Z0
Stack
Lec 19 : Computation Theory Equivalence of PDAs and CFGs
9
12- read nothing, pop nothing, push nothing move to q2 and
accept
H.W
Convert CFG below to PDA
S? XSX / aY
X? Y / S
Y?
q0
q0
q1
?,Z\SZ q2
?,S\?,0S0S
?,S\?,1S0
?,S\?,1
1,1\?
0,0\?
?,Z\Z
0 1 0 1 1 0
Input String
Z0
Stack