# Automata CFG to PDA Conversion

Automata CFG to PDA Conversion with automata tutorial, finite automata, dfa, nfa, regexp, transition diagram in automata, transition table, theory of automata, examples of dfa, minimization of dfa, non deterministic finite automata, etc.

# 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 0104 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 0104 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
```

Next TopicTuring Machine