Join 3,572 readers in helping fund MetaFilter (Hide)


How do you determine if a dfa is minimal
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)
 
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


« Older How do I stop the mouse pointe...   |  I need a name for my X-files t... Newer »
This thread is closed to new comments.