CFG to PDA Conversion

The first symbol on R.H.S. production must be a terminal symbol. The following steps are used to obtain PDA from CFG is:

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  

Example 1:

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, ε)}

Example 2:

Construct PDA for the given CFG, and test whether 0104 is acceptable by this PDA.

S → 0BB  

B → 0S | 1S | 0  

Solution:

The PDA can be given as:

A = {(q), (0, 1), (S, B, 0, 1), δ, q, S, ?}  

The production rule δ can be:

R1: δ(q, ε, S) = {(q, 0BB)}

R2: δ(q, ε, B) = {(q, 0S) | (q, 1S) | (q, 0)}

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

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

Testing 010⁴ i.e. 010000 against PDA:

δ(q, 010000, S) ⊢ δ(q, 010000, 0BB)  

                ⊢ δ(q, 10000, BB)              R1  

                ⊢ δ(q, 10000,1SB)              R3    

                ⊢ δ(q, 0000, SB)               R2        

                ⊢ δ(q, 0000, 0BBB)             R1     

                ⊢ δ(q, 000, BBB)               R3        

                ⊢ δ(q, 000, 0BB)               R2      

                ⊢ δ(q, 00, BB)                 R3     

                ⊢ δ(q, 00, 0B)                 R2    

                ⊢ δ(q, 0, B)                   R3    

                ⊢ δ(q, 0, 0)                   R2  

                ⊢ δ(q, ε)                      R3    

                  ACCEPT  

Thus 010⁴ is accepted by the PDA.

Example 3:

Draw a PDA for the CFG given below:

S → aSb  

S → a | b | ε  

Solution:

The PDA can be given as:

P = {(q), (a, b), (S, a, b, z0), δ, q, z0, q}  

The mapping function δ will be:

R1: δ(q, ε, S) = {(q, aSb)}

R2: δ(q, ε, S) = {(q, a) | (q, b) | (q, ε)}

R3: δ(q, a, a) = {(q, ε)}

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

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

Simulation: Consider the string aaabb

δ(q, εaaabb, S) ⊢ δ(q, aaabb, aSb)             R3  

                ⊢ δ(q, εaabb, Sb)              R1                                 

                ⊢ δ(q, aabb, aSbb)             R3  

                ⊢ δ(q, εabb, Sbb)              R2  

                ⊢ δ(q, abb, abb)               R3  

                ⊢ δ(q, bb, bb)                 R4  

                ⊢ δ(q, b, b)                   R4  

                ⊢ δ(q, ε, z0)                  R5  

                ⊢ δ(q, ε)  

                ACCEPT