# Minimization of an DFA

Before minimizing an AFD, it must be completed, ie add a bin state named R on the automaton below.

Myhill-Nerode’s theorem. Let L be a rational language. Of all the DFA recognizing L, there is one and only one that has a minimal number of states.

The minimization algorithm is as follows:

1. Complete the DFA named D
2. Construct an initial partition Π containing two sets I and II of states such that Π = {I = (terminal states of D), II = (other states of D)}
3. For each state of D do
1. Build the transition table
2. Mark departure and arrival states by their group in Π
4. If states of the same group of Π have diverging behaviors
1. Separate the states into a new group (III for example) – preferably only one separation by iteration.
5. End: new states are groups of Π

## Example

Let’s take the example of the DFA above. It is very deterministic as shown by the transition table.

Let’s look at the transition table in step 3:

 a b c 0(I) 2(II) 5(II) R(I) 2(II) R(I) R(I) R(I) 5(II) R(I) R(I) 8(II) 8(II) R(I) R(I) 8(II) R(I) R(I) R(I) R(I)

Let’s take the example of the DFA above. It is deterministic as shown by the transition table.

Let’s look at the transition table in step 3:

 a b c 0(I) 2(II) 5(II) R(III) 2(II) R(III) R(III) R(III) 5(II) R(III) R(III) 8(II) 8(II) R(III) R(III) 8(II) R(III) R(III) R(III) R(III)

We notice when in group II, the behavior of 2 and 5, 8 diverge, so we will separate them into two groups: II = (5, 8) and IV = (2)

Here is the new transition table:

 a b c 0(I) 2(IV) 5(II) R(III) 2(IV) R(III) R(III) R(III) 5(II) R(III) R(III) 8(II) 8(II) R(III) R(III) 8(II) R(III) R(III) R(III) R(III)

There is no more divergence between the groups, so we can perform the transition table with the minimized DFA giving the following transition table:

 a b c I IV II III IV III III III II III III II III III III III

The initial state is I (in relation to its equivalent in D), and the terminal states of the automaton are II and IV (in relation to their equivalents in D).

## Another example

Take the following automaton:

The initialization phase makes it possible to obtain the non-terminal group I and the terminal group II:

 A B C D Init I II I II

Let’s look at the transitions for each state according to groups I and II:

 Alphabet A B C D a II II I II O I II I II

Then we perform the separation of the sets. Two states are in the same set if they were already in the same set and if the transitions lead in the same sets. In this example, B and D behave exactly the same way, so they stay together. On the other hand, A and C which were part of the same set behave differently on the symbol « a ». Therefore, the set noted I divides into two. So we get:

 A B C D Init I II I II a II II I II 0 I II I II Separation 1 I II III II

The current situation (the Separation 1 line) is different than the starting situation. So we must start again.

 A B C D Init I II I II a II II I II 0 I II I II Separation 1 I II III II A II II III II 0 III II III II Separation 2 I II III II

The line « Separation 2 » is identical to the line « Separation 1 ». Therefore, in each of the remaining sets, the states are not distinguishable (they behave in exactly the same way and are therefore « redundant »).

So we can build the new automaton by associating a state with each set. The transitions are indicated by the table. The initial state is the one containing the initial state of the starting automaton: here I contains the state A, initial state. The final states are the states whose corresponding set contains at least one final state: here, II contains B and D which are final.

For now, we have « merged » indistinguishable states. We must now delete all remaining useless states. In our example, state III is a sterile state (non-terminal and without transition), therefore useless. It must therefore be deleted. Hence the minimal deterministic automaton of the following figure: