TAS Must Die, Chapter 3

It isn't hard to generate a lexer that has some identical states in it. Identical states aren't wrong, but they are bulky and aesthetically offensive. Removing them will reduce the size of the FA and is a good idea in general.


It's pretty easy to see that states 1 and 4, 2 and 5, and 3 and 6 are functionally identical. It gets less easy when you generate an NFA that has 200 states in it.

So how do we recognize when states are functionally identical?

My first stab was equivalent to trying to reassemble a broken ceramic sculpture by trying all the pieces and parts to see if they fit. It occured to me that testing a universe of disparate states for sameness was not going to be effective. If you have A->x->Z and B->x->Q, you can't tell if A and B are identical because at some stage in the process you may or may not have tested Z and Q for sameness.

It occured to me that it's easier to prove states are different than it is to prove they're the same.
The algorithm below starts off with all the states in a large group. We iterator over the states in the group, querying each for a 'signature' of it's transitions and such. We create new groups and put all states with the same signature in the same group. The signatures are not dependent upon only the states' transitions, but also on the destination group of those transitions. That is, S1->x->s10 and S2 -> x -> S9 look different. But if s10 and s9 are both in group 6, then signature(S1) could be something like "x->G7" and signature(S2) could be "x->G7". That's a match. S1 and S2 could be identical.

make a group G
for each state S
{
G.add(s), where this method includes
 s.groupMember = G
}

while(the number of groups keeps changing)
{
for each group g
  {
  Regroup the states in g into g1, g2, ... gn
    based upon signature(state). Whenever
    adding a state to a group, we must
    be sure to set s.groupMember = owningGroup
  }
}

// All groups now contain only redundent states.
For each group G
{
make a new uber state S as a copy of any
   member state.
associate S with G
}

// Change the references to the old obsolete
// states with the shiny new uber-states.
For each group G
  {
  for each of G's uberstate's transitions T
     {
     T.getDestination = T.getDestinationState.
                    getGroupMember.
                    getUberstate
     }
  }

startState = startState.getGroupMember.getUberstate
end

String signature(state)
{
make a comparable representation of the transitions
and the group number of which the transition's
destination state is a member.  If some state S has
transitions x->10, y->11, and z->12, and the groups
are grp#0 = (10 11) and grp#1 = (12), then the result
could be the (well delimited) "~x->0~~y->0~~z->1~"

Also add to the string if the state is stop state,
or any other identifying fact, such as the token
class to be produced by the state.  For example
if two states are identical except one produces
a token class of A and the other produces a
token class of B, they aren't identical.

Two states that produce a different result can't
possibly be identical. Either they have different
inputs or the destinations fundamentally different.

Two states that do seem to be identical now could be
proven to be non-identical in a different iteration
of the loop.
}