Home Â» Automata CFG to PDA Conversion

# 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

Next TopicTuring Machine