**CFG to PDA**

• Given: A context free grammar G

• Construct: A pushdown automata M

• Such that:

Language generated by G is the same as Language accepted by M.

•

Let’s formalize this:

Let G = (V, T, S, P) be a context

free grammar.

We define a pushdown automata

• M = (Q, Σ, Γ ,δ, q0, Z0 ,F)

Such that

• L(M) = L(G)

Step 6: CFG → PDA

Pushdown Automata :

• Basic idea

Use the stack of the PDA to simulate the

derivation of a string in the grammar.

• Push S (start variable of G) on the stack

• From this point on, there are two moves the PDA

can make:

1. If a variable A is on the top of the stack,pop

it and push the right-hand side of a production

A → β from G.

2.If a terminal, a is on the top of the stack,

pop it and match it with whatever symbol is being read from the tape.

Step 2: CFG → PDA

Step 5: CFG → PDA

Step 7: CFG → PDA

Step 4: CFG → PDA

Let’s formalize this :

Step 1: CFG → PDA

Step 8: CFG → PDA

• Let’s look at an example:

Remember the CFG for odd

length

palindromes:

• S → a | b

• S → a S a | b S b

Let’s convert this to a

PDA

.

Step 9: CFG → PDA

•

Example:

M = (Q, Σ, Γ ,δ, q0, Z0 ,F)

Q = { q0, q1, q2 }

Σ = { a, b }

Γ = { a, b, S, Z0 }

F = { q2 }

Step 10: CFG → PDA

Lots of moves

(see next slide)

Step 11: CFG → PDA

Let us convert the expression Grammar to PDA

The Grammar is:

I → a | b | Ia | Ib | I0 | I1

E → I | E*E | E+E | (E)

Step 12: CFG → PDA

• Let’s run M on abbba

(q0, abbba, Z) a (q1, abbba, SZ)

a (q1, abbba, aSaZ) // push

a (q1, bbba, SaZ) // match

a (q1, bbba, bSbaZ) // push

a (q1, bba, SbaZ) // match

a (q1, bba, bbaZ) // push

a (q1, ba, baZ) // match

a (q1, a, aZ) // match

a (q1, ε, Z) // match

a (q2, ε, Z ) // accept

The set of input symbols for PDA is {a, b, 0, 1, (,), +, *}. These eight symbols and the

symbols I and E from the stack alphabet. The transition function for the PDA is

a) δ(q, ε, I) = {(q, a), (q, b),

(q, Ia), (q, Ib), (q, I0), (q, I1)}

b) δ(q, ε, E) = {(q, I),(q, E+E),

(q,E*E),(q, (E))}

c) δ(q, a, a) = {(q, ε)}; δ(q, b, b) =

{( q, ε)}; δ(q, 0, 0) = {(q, ε)};

δ(q, 1, 1) = {(q, ε)}; δ(q,),() = {(q, ε)}; δ(q, ), )) = {(q, ε)}; δ(q, +, +) = {(q, ε)}; δ(q, *, *) = {(q, ε)}

Note that (a) and (b) come from rule (1), while the eight transition of (c) come from rule (2). Also, δ is empty except as defined by (a) through (c).

Try Another one

END