How do you determine if a dfa is minimal

April 20, 2008 12:19 PM

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)

Did you try google?
posted by b1tr0t at 1:11 PM on April 20, 2008

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

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

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