Minimization of an DFA

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

langage22

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.
    2. Return to 3
  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:

langage59

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.

langage60.gif

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:

langage61

Publicités