Minimisation of Finite State Automata

Algorithm

The following algorithm generates a total FSA equivalent to the one we start off with but with the least possible number of states. Note, however, that useless and unreachable states would first have to be removed for the algorithm to work. Also, the finite state automaton must be deterministic.

1. First make the FSA total (see the relevant algorithm);
2. Relabel the nodes 1, 2, ... n (where n is therefore the number of states);
3. Construct an nxn matrix D(0) such that the entry D(0)_i,j is TRUE if one of the states i, j is final while the other is not. The entry is FALSE otherwise (both i, j are final or both non-final states);
4. Given matrix D(k) we can construct matrix D(k+1) as follows: D(k+1)_i,j is TRUE if D(k)_i,j was TRUE or there is an input a such that starting from state i with input a takes us to a state i' and stating from state j with input a takes us to a state j' such that D(k)_i',j' is TRUE. Otherwise, the entry D(k+1)_i,j remains marked FALSE.
5. Repeat the previous step until D(k+1)_i,j is the same as D(k)_i,j. Call this final matrix D.
6. We now know that state i is indistinguishable from state j if and only if D_i,j is FALSE - join together the indistinguishable states

Example

Consider the following FSA:

1. Start by making the FSA total:

   

2. Enumerate the states:

   

3. Construct D(0):

   FALSE	TRUE	FALSE	FALSE
   TRUE	FALSE	TRUE	TRUE
   FALSE	TRUE	FALSE	FALSE
   FALSE	TRUE	FALSE	FALSE

4. Construct D(1) from D(0):

   FALSE	TRUE	FALSE	TRUE
   TRUE	FALSE	TRUE	TRUE
   FALSE	TRUE	FALSE	TRUE
   TRUE	TRUE	TRUE	FALSE

5. Construct D(2) from D(1):

   FALSE	TRUE	FALSE	TRUE
   TRUE	FALSE	TRUE	TRUE
   FALSE	TRUE	FALSE	TRUE
   TRUE	TRUE	TRUE	FALSE

6. Since D(2) and D(1) are identical, we conclude that states 1 and 3 are indistinguishable (since D(2)_1,3 is equal to FALSE).
7. Finally we coalesce indistinguishable states:

   

Exercises

Minimise the following FSA: