Minimization of FSM's

Another question of interest is whether a given FSM has ``redundant'' states. That is, is it as small as it can be or is there a smaller machine, i.e., one with fewer states, that can recognize the same language.

So the idea is, given a machine, to see whether it has redundant states. The first step is to determine whether two states in the machine are distinguishable, i.e., whether there is some string such that when the machine is started in the respective states, one computation will lead to an accepting state and the other won't. The following specification defines (and computes) distinguishable states.

% Assume Mach is a deterministic machine
% S1 and S2 are distinquishable if S1 is final and S2 is not.
distinguishable(Mach,S1,S2) :-
        mfs(Mach,S1),
        is_state(Mach,S2),
        tnot(mfs(Mach,S2)).
% S1 and S2 are distinquishable if S2 is final and S1 is not.
distinguishable(Mach,S1,S2) :-
        mfs(Mach,S2),
        is_state(Mach,S1),
        tnot(mfs(Mach,S1)).
% S1 and S2 are distinguishable if some symbol Sy takes them to states that
%    are distinguishable.
distinguishable(Mach,S1,S2) :-
        m(Mach,S1,Sy,T1),
        m(Mach,S2,Sy,T2),
        distinguishable(Mach,T1,T2).

The first two rules say that states are distinguishable if one is final and the other is not. For this we need the constraint that the initial machine be deterministic. The third rule says that states are distinguishible if there is a symbol on which they make transitions to distinguishable states.

As an example of finding distinguishable states, we can use the following machine:

m(dfa,a,0,b).
m(dfa,a,1,f).
m(dfa,b,0,g).
m(dfa,b,1,c).
m(dfa,c,0,a).
m(dfa,c,1,c).
m(dfa,d,0,c).
m(dfa,d,1,g).
m(dfa,e,0,h).
m(dfa,e,1,f).
m(dfa,f,0,c).
m(dfa,f,1,g).
m(dfa,g,0,g).
m(dfa,g,1,e).
m(dfa,h,0,g).
m(dfa,h,1,c).

mis(dfa,a).
mfs(dfa,c).

(draw a picture. Could also use the determistic version of ms0s1s2, since it has an extra state q0, I think.)

And with this machine we get the following evaluation:

| ?- distinguishable(dfa,S1,S2),S1@<S2,writeln(d(S1,S2)),fail.
d(d,e)
d(d,g)
d(d,h)
d(b,d)
d(b,e)
d(b,f)
d(b,g)
d(b,c)
d(a,b)
d(a,d)
d(a,f)
d(a,g)
d(a,h)
d(a,c)
d(f,g)
d(f,h)
d(e,f)
d(e,g)
d(e,h)
d(g,h)
d(c,d)
d(c,e)
d(c,h)
d(c,g)
d(c,f)

no
| ?-

In the query we filtered to keep only the cases in which the first state has a smaller name than the second. This was just to avoid printing out all the commutative and reflexive pairs.

What is more interesting than finding two states that are distinguishable is finding two states that are not distinguishable. In this case one of the states is unnecessary and can be eliminated from the machine. So using this definition of distinguishable, we can construct a minimal DFSM that accepts the language given by a machine by merging indistinguishable states in that machine.

% min (assuming the machine is deterministic), reduce by
%   indistinguishability. 
m(min(Mach),So,Sy,Ta) :-
    reachable(min(Mach),So),
    member(Ss,So),
    m(Mach,Ss,Sy,T),
    tsetof(S,indistinguishable(Mach,T,S),Ta).

% The initial (final) state is the set of states indistinguishable
%   from the initial (final) state of the base machine. 
mis(min(Mach),IS) :-
    mis(Mach,Bis),
    tsetof(S,indistinguishable(Mach,Bis,S),IS).
mfs(min(Mach),FS) :-
    mfs(Mach,Bfs),
    tsetof(S,indistinguishable(Mach,Bfs,S),FS).

indistinguishable(Mach,S1,S2) :-
    is_state(Mach,S1),
    is_state(Mach,S2),
    tnot(distinguishable(Mach,S1,S2)).

And executing this with the previous example, we get:

| ?- m(min(dfa),S,Sy,T),writeln(m(min(dfa),S,Sy,T)),fail.
m(min(dfa),[a,e],1,[f])
m(min(dfa),[a,e],0,[b,h])
m(min(dfa),[f],1,[g])
m(min(dfa),[f],0,[c])
m(min(dfa),[b,h],1,[c])
m(min(dfa),[b,h],0,[g])
m(min(dfa),[g],1,[a,e])
m(min(dfa),[g],0,[g])
m(min(dfa),[c],1,[c])
m(min(dfa),[c],0,[a,e])

no
| ?- mfs(min(dfa),S),writeln(mfs(min(dfa),S)),fail.
mfs(min(dfa),[c])

no
| ?- mis(min(dfa),S),writeln(mis(min(dfa),S)),fail.
mis(min(dfa),[a,e])

no
| ?-

(Draw state diagram) Note that the state ``d'' does not appear in this collapsed machine. This is because it has no in-transitions and is not the initial state, so it doesn't appear in our reduction. It is actually equivalent to state ``f'', and could be merged with it.