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: a compound state 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: