April 20, 2008 12:19 PM Subscribe

Is there an elegant algorithm to determine if a dfa is minimal? Obviously you can minimize a dfa and then check to see if the result is isomorphic to the original. Is there another way?

posted by rdr to Computers & Internet (4 answers total)

posted by rdr to Computers & Internet (4 answers total)

That's not what I asked. I'm not asking how to build a minimal dfa. I'm asking if there's a way to test if a dfa is minimal.

posted by rdr at 1:30 PM on April 20, 2008

posted by rdr at 1:30 PM on April 20, 2008

It seems like all you have to check for is unreachable states and equivalent states. If there aren't any of either, the DFA is minimal.

You can check for equivalent states by looking at the transition function. If delta(*q*, *a*) = delta(*r*, *a*) for all *a* in the alphabet and two states *q* and *r*, the states are equivalent.

Unreachable states are ones that have no path from the initial state.

posted by zixyer at 2:14 PM on April 20, 2008

You can check for equivalent states by looking at the transition function. If delta(

Unreachable states are ones that have no path from the initial state.

posted by zixyer at 2:14 PM on April 20, 2008

Thanks. Once I read your answer I can see how your answer is implied by how subset construction terminates.

posted by rdr at 2:42 PM on April 20, 2008

posted by rdr at 2:42 PM on April 20, 2008

This thread is closed to new comments.

posted by b1tr0t at 1:11 PM on April 20, 2008