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.
No comments:
Post a Comment