Scribd
Upload
19 views3 pages

Pda To CFG

The document outlines the conversion of a Pushdown Automaton (PDA) to a Context-Free Grammar (CFG) by detailing the production rules derived from PDA moves. It provides specific examples of how erasing and non-erasing moves translate into CFG productions, culminating in a total set of productions. The final step involves reducing the grammar to obtain the required CFG for the given PDA.

Uploaded by

varshitha2k5
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views3 pages

Pda To CFG

The document outlines the conversion of a Pushdown Automaton (PDA) to a Context-Free Grammar (CFG) by detailing the production rules derived from PDA moves. It provides specific examples of how erasing and non-erasing moves translate into CFG productions, culminating in a total set of productions. The final step involves reducing the grammar to obtain the required CFG for the given PDA.

Uploaded by

varshitha2k5
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

PDA to CFG

The productions in ‘p’ are induced by moves of


PDA as follows:
 S productions are given by S→ [q0z0q] for
every q belongs to Q.
 Each erasing move δ(q,a,z)=(q`,ε) induces
production [qzq`] → a
 Each non erasing move
δ(q,a,z)=(q1,z1,z2,…..zm) induces many
productions of the form [qzq`] →
a[q1z1q2][q2z2q3]………[qmzmq`]
Example:
Construct CFG for the given PDA
A=({q0,q1},{a,b},{z0,z},δ,q0,z0,Ø)
Where δ is given as
1. δ(q0,b,z0) = (q0,zz0)
2. δ(q0,ε,z0) = (q0,ε)
3. δ(q0,b,z) = (q0,zz)
4. δ(q0,a,z) = (q1,z)
5. δ(q0,b,z) = (q1,ε)
6. δ(q1,a,z0) = (q0,z0)
Soln:
Rule 1:
S→ [q0z0q] for every q∈Q
From rule 1 we get
I. S→ [q0z0q0]
II. S→ [q0z0q1]
1.δ(q0,b,z0) = (q0,zz0) //push
Rule3:
 Each non erasing move δ(q,a,z)=(q1,z1z2…..zm) induces many productions
of the form
[qzq`] → a[q1z1q2][q2z2q3]………[qmzmq`]
q=q0, a=b,z=z0 , q0=q1,z1=z,z2=z0
I. [q0z0q0]→ b[q0zq0][q0z0q0]
II. [q0z0q0]→ b[q0zq1][q1z0q0]
III. [q0z0q1]→ b[q0zq0][q0z0q1]
IV. [q0z0q1]→ b[q0zq1][q1z0q1]

2. δ(q0,ε,z0) = (q0,ε) // pop


 Each erasing move δ(q,a,z)=(q`,ε) induces
production [qzq`] → a
I. [q0z0q0] → ε

3. δ(q0,b,z) = (q0,zz) //push


I. [q0zq0]→b[q0zq0][q0zq0]
II. [q0zq0]→b[q0zq1][q1z q0]
III. [q0zq1]→b[q0zq0][q0z q1]
IV. [q0zq1]→b[q0zq1][q1z q1]

4. δ(q0,a,z) = (q1,z) //skip


I. [q0zq0]→a[q1zq0]
II. [q0zq1]→a[q1zq1]

5. δ(q0,b,z) = (q1,ε) //pop


I. [q0zq1] → b

6. δ(q1,a,z0) = (q0,z0) //skip


I. [q1z0q0] →a[q0z0q0]
II. [q1z0q1] →a[q0z0q1]
Total productions
S→ [q0z0q0]|[q0z0q1]
S→A|B
[q0z0q0]=A
[q0z0q1]=B
[q0zq0]=X
[q0zq1]=Y
[q1z0q0]=C
[q1z0q1]=D
[q1zq0]=E
[q1zq1]=F

I. S→A|B
II. A →bXA|bYC|ε
III. B →bXB|bYD
IV. X →bXA|bYE|aE
V. Y →bXY|bYF|aF|b
VI. C →aA
VII. D →aB
Now reduce the grammar and obtain the required CFG.

You might also like