# NFA to DFA

Starting from a NFA, build an equivalent DFA by removing nondeterministic-transitions.

The idea: if state $q$ can reach both $r$ and $s$ via `a`

:

- $q\xrightarrow{a}r$
- $r\xrightarrow{a}s$

then create a new *compound* state $rs$ that $q$ can reach via `a`

- $q\xrightarrow{a}rs$

The *compound* state $rs$ has the outward transitions of both $r$ and $s$.

Of course, this means we can have *up to* $2^n$ states — but in practice, most of them are junk states which we ignore.

## Original automaton

We will convert the following NFA:

Which accepts words ending in `ab`

— language: $(a|b){*}\ ab$. Examples: `ab`

, `bbbab`

, `aabbbbaaab`

. Transition table:

$\delta$ | a | b |
---|---|---|

$\bf{q_0}$ | $q_0, q_1$ | $q_0$ |

$\bf{q_1}$ | $q_2$ | |

$\bf{q_2}$ |

## Transition function

The table will have the same columns, `a`

and `b`

. We start with the row for $q_0$ and add a new row for each new state encountered.

$\delta’$ | a | b |
---|---|---|

$\bf{q_0}$ |

From $q_0$, via `b`

it can reach only itself — no non-determinism here, keep it the same. Via `a`

it can reach both itself and $q_1$ — create a *compound* state labeled $q_{01}$.

Note: acompoundstate is not a list of states. It is a single state which has a different label ($q_{01}$), as it is simpler for us to work with it. We could have labeled it $q_3$ or $q_a$ just as well (but not the same as an existing state).

Add another row for the newly-encountered state $q_{01}$.

From $q_{01}$, via `a`

it can reach *everything* $q_0$ and $q_1$ can reach via `a`

:

- $\delta(q_0,a) = \langle q_0,q_1 \rangle$
- $\delta(q_1, a)= \emptyset$
- so $\delta’(q_{01},a) = q_{01}$

$q_{01}$, via `b`

can reach *everything* $q_0$ and $q_1$ can reach via `b`

:

- $\delta(q_0,b) = \langle q_0 \rangle$
- $\delta(q_1, b)= \langle q_2 \rangle$
- so $\delta’(q_{01},b) = q_{02}$

Again, we add another row for each new state encountered: $q_{01}$ already exists so we add $q_{02}$.

After completing this row in the same manner, there are no new states encountered. No rows must be added — we finished the transition table.

$\delta’$ | a | b |
---|---|---|

$\bf{q_0}$ | $q_{01}$ | $q_0$ |

$\bf{q_{01}}$ | $q_{01}$ | $q_{02}$ |

$\bf{q_{02}}$ | $q_{01}$ | $q_0$ |

## Starting and accepting states

The starting state remains $q_0$.

A *compound* state is accepting iff one of the states in its label is accepting (in the original automaton). In our case, the original automaton had only one accepting state, $q_2$ which appears only in the label of state $q_{02}$.

## Converted automaton

We obtained a bigger automaton which *deterministically* accepts the same language $(a|b){*}\ ab$

The states can be renamed without affecting functionality — $q_{01}$ to $q_1$ and $q_{02}$ to $q_2$.

$\delta’$ | a | b | accepting |
---|---|---|---|

$\rightarrow \bf{q_0}$ | $q_1$ | $q_0$ | |

$\bf{q_{1}}$ | $q_1$ | $q_2$ | |

$\bf{q_{2}}$ | $q_1$ | $q_0$ | ✓ |

## IO

Read the definition of an NFA and print the definition of an equivalent DFA.

## Input `NFA.definition`

```
2
0 a 0
0 b 0
0 a 1
1 b 2
```

Accepting states on the first line; entries in the transition table on subsequent lines.

## Example output `DFA.definition`

```
2
0 a 1
0 b 0
1 a 1
1 b 2
2 a 1
2 b 0
```

Definition of the DFA. It is not the only DFA equivalent to the original NFA — depending on the method you chose, your output may vary.

To verify equivalence we would have to check the output of both atomata on every possible input. Since this is an infinite set, we will settle with just a small relevant subset.

## Input `NFA.tests`

```
ab
bbbab
aabbbbaaab
bba
baba
bb
aaa
```

```
1
1
1
0
0
0
0
```

Words to test on the converted automaton.

# Another conversion

## Input `NFA.definition`

```
2
0 a 0
0 a 1
0 b 2
1 a 0
1 b 1
2 b 0
2 b 1
```

## Example output `DFA.definition`

```
2 3
0 a 5
0 b 2
5 a 5
5 b 3
3 a 0
3 b 5
2 a 6
2 b 5
6 a 6
6 b 6
```

## Input `DFA.tests`

```
b
aaab
bbb
bbab
a
aaaa
bb
bbaa
bbba
```

```
1
1
1
1
0
0
0
0
0
```

## More examples

Narrated transformations: