From NFA to DFA (determinization)

Rabin-Scott’s theorem says that any language recognized by an indeterministic finite automaton can be recognized by a deterministic finite state automaton. It is therefore possible to represent an indeterministic automaton by a deterministic automaton, this process is called determinization.

For example, consider the following non-deterministic finite state automaton (K, T, M, I, F):K = {S1, S2, S3, S4}
T = {a, b, c}
M = {(S1, a, S1),(S1, a, S3),(S2, b, S2),(S2, b, S3),(S3, c, S3),(S3, c, S4)}
I = {S1, S2}
F = {S4}
corresponding to the following graph:

langage9

The states of the deterministic finite state automaton (DFA) and their transition function are then constructed. Initially, it has a single state which is composed of the set of initial states of the indeterminate finite state automaton (NFA): in our example, the initial state of the DFA is {S1, S2}.

Whenever a new state is added to the DFA, its transition function is determined by joining the corresponding lines in the NFA transition table: in our example, for the state {S1, S2}, we make the union of the lines corresponding to S1 and S2, and we determine the transition function

langage10

In other words, in the state « S1 or S2 » on can reach the states « S1 or S3 » (M ({S1, S2}, a) = {S1, S3 }) by reading letter a; in the state « S1 or S2 » one can read letter b, one goes in the state « S2 or S3 » (M ({S1, S2}, b) = {S2, S3 }) and when one is in the state « S1 or S2 » and one reads letter c, one goes in the state « empty », corresponding to the state of error (M ({S1, S2}, c) = ∅.

The states {S1, S3} and {S2, S3} are then added to the DFA and their transition functions are determined according to the same process. Step by step, we build the following transition table for the DFA:

langage11

The set of states of the DFA is K ‘= {{S1, S2}, {S1, S3}, {S2, S3}, {S3, S4}}. DFA states containing a final state of NFA are final states. Here, the NFA has only one final state S4 and the set of final states of the DFA is F ‘= {{S3, S4}}. This DFA corresponds to the following graph:

langage12

Another exemple, another way to explain

langage53

Practically, one only builds the states accessible from I, step by step: one starts from the initial state I, then one calculates all the transitions starting from I, then one starts again with the new states obtained, etc.

initial state: I = {1} transition by a: {1, 2} transition by b: {1}. We just did {1} so we’ll do {1,2}

state {1, 2} transition by a: {1, 2} transition by b: {1, 3}, we now do {1,3}

state {1, 3} transition by a: {1, 2} transition by b: {1}. There is no unvisited state left. Only the state {1,3} contains a terminal state, so {1,3} is terminal.

Which gives us the following DFA:

langage54

The calculation by the tables is much more readable.

delta a b
1 {1,2} {1}
2 {3}
3

Let’s calculate the delta DFA states:

Detla prime a b
1 {1,2} 1
{1,2} {1,2} {1,3}
{1,3} {1,2} {1}

The second line creates us the state {1,3}. We notice that in the end, the automaton is the same as that compute with the previous method (state 3 is not useful since nobody calls it).