# Convert following PDA – CFG

PDA – CFG is the important topic of the Subject Theory Of Computation.

**Solution: **

**Step 1: Add the production for the start symbol**

Sà[q z q]

Sà[q z p]

**Step 2: Add production for the δ( q, 1, z) →(q ,xz)**

[q z q]→1[q x q][q z q]

[q z q]→1[q x p][p z q]

[q z p]→1[q x q][q z p]

[q z p]→1[q x p][p z p]

**Step 3: Add production for the δ( q, 1, x) →(q ,xx)**

[q x q]→1[q x q][q x q]

[q x q]→1[q x p][p x q]

[q x p]→1[q x q][q x p]

[q x p]→1[q x p][p x p]

**Step 4: Add the production for δ( q, ^, x) →(q ,^)**

[q x q]→^

**Step 5: Add the production for δ( q, 0, x) →(p ,x)**

[q x q]→0 [p x q]

[q x p]→0 [p x p]

###### S**tep 6: Add the production for δ( p, 1, x) →(p ,^)**

[p x p]→1

**Step 7: Add the production for δ( p, 0, z) →(q ,z)**

[p z q]→0 [q z q]

[p z p]→0 [q z p]

**Step 8: Renaming variable name**The set of production can be written as:

SàA|B

A→1EA|1FC B→1EB|1FD

E→1EE|1FG

F→1EF|1FH

E→^

E→0G

F→0H

H→1

C→0A

D→0B

**Step 9: simplification of grammar**

Symbol G is not available on left side of grammar so, it can be eliminated.

S→A|B

A→1EA|1FC

B→1EB|1FD

E→1EE|^

F→1EF|1FH|0H

H→1

C→0A

D→0B

**Related Terms**

Theory of Computation, Finite Automata, Union, Intersection & Compliment operation, Context Free Grammar

## Leave a Reply