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:

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

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:

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:

## Another exemple, another way to explain

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:

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).