Question

Write the procedure to convert CFG to PDA and also convert the following CFG to PDA
S -> B | aBB
A -> aBB| a
B -> Bbb| a
C -> a​

Answer 1

Answer:

I don't know u r answer hehehehe

Explanation:

but I know rules

Step 1: Convert the given productions of CFG into GNF.

Step 2: The PDA will only have one state {q}.

Step 3: The initial symbol of CFG will be the initial symbol in the PDA.

Step 4: For non-terminal symbol, add the following rule:δ(q, ε, A) = (q, α)

Where the production rule is A → α

Step 5: For each terminal symbols, add the following rule:

δ(q, a, a) = (q, ε) for every terminal symbol Convert the following grammar to a PDA that accepts the same language.

S → 0S1 | A

A → 1A0 | S | ε

Solution:

The CFG can be first simplified by eliminating unit productions:

S → 0S1 | 1S0 | ε Now we will convert this CFG to GNF:

S → 0SX | 1SY | ε

X → 1

Y → 0

The PDA can be:

R1: δ(q, ε, S) = {(q, 0SX) | (q, 1SY) | (q, ε)}

R2: δ(q, ε, X) = {(q, 1)}

R3: δ(q, ε, Y) = {(q, 0)}

R4: δ(q, 0, 0) = {(q, ε)}

R5: δ(q, 1, 1) = {(q, ε)}