Mumbai University > Computer Engineering > Sem 4 > Theoretical Computer Science

Marks: 10M

Year: Dec 2016

For converting CFG to PDA we will follow following steps

Step1: Convert given grammer to CNF

Step2: The PDA should be designed by initially pushing start symbol. Then immediately perform POP operation

Step3: Then for each production perform corresponding PUSH and POP operation.

S->XA|€

A->bB can be written as

A->YB

So, B->Y

Hence,

S->XA|€

A->YB

B->Y

Which is the required CNF

Now for PDA we have two rules,

i. δ(q, ^, A)={(q, α)| A->α is in P}

ii. δ(q,a,a)={(q, ^)} for every a€ T

δ can be defined by the following rules

(A) δ(q, ^, S)={(q, X, A), (q, €)}

(B) δ(q, ^, A)={(q, Y, B)}

(C) δ(q, ^, B)={(q, Y)}

(D) δ(q, 0, 0)={(q, ^)}

(E) δ(q, 1, 1)={(q, ^)}