Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have probably a pretty dumb question about the classical Minimization algorithm for a DFA, as described in the Hopcroft book "Introduction to Automata Theory, Languages and Computation", pg. 155-164.

I have no problem with the algorithm itself, or with the examples or even the problems in the book, but the algorithm as described does not seem to work for certain DFAs which are composed entirely of final states.

For example, I tried running this algorithm manually on the automaton from pg.8, fig. 5(a), "Speech Recognition with Weighted-Finite State Transducers" (Mohri) after making all the states final and removing the weights for the sake of simplicity. The resulting automaton is then,

http://i.imgur.com/BDDuT.png (rendered with OpenFST)

however, no matter how I read the description in the book, I cannot find a way to get the table-filling algorithm to do anything with this. It's a non-starter as all the states are already final. But clearly states (1) and (2) should be merged.

My best guess at the moment is that I am interpreting the delta function either incorrectly or too strictly given the wording. That is, for example, in the case of delta(2,e) and delta(3,e), delta(2,e) is accepting and delta(3,e) does not exist. Is that non-existence then also equivalent to 'non-accepting'? From the wording of the book I'm strongly inclined to say that this is not true - that this should be ignored and only existing transitions should be considered, but in that case this pathological example does not end up minimized; the algorithm is just dead in the water before it starts.

I've looked through many other papers and resources online but they all seem to gloss over this which makes me think I'm just a total moron. Any advice for this wayward traveler would be greatly appreciated.

share|improve this question
    
Perhaps this is the problem? If every state is final/accepting, then the automaton accepts every input, and is equivalent to just a one-state accepting automaton that ignores its input? –  Joseph O'Rourke Jun 30 '10 at 13:18
add comment

1 Answer

I don't have access to the book, but maybe the way it presents the algorithm requires the DFA to be complete. In your example this would mean that all missing transitions should be completed by transitions to a special fail state $q_f$, which is non-accepting. Apply the minimization algorithm after that operation, then you can remove $q_f$ and you should get the minimal 3-state DFA.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.