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:
Where the production rule is A → α
Step 5: For each terminal symbols, add the following rule:
Example 1:
Convert the following grammar to a PDA that accepts the same language.
Solution:
The CFG can be first simplified by eliminating unit productions:
Now we will convert this CFG to GNF:
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.
Solution:
The PDA can be given as:
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 0104 i.e. 010000 against PDA:
Thus 0104 is accepted by the PDA.
Example 3:
Draw a PDA for the CFG given below:
Solution:
The PDA can be given as:
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