automatadfanfa

When minimizing DFAs through table fill, should a pair of final states transition to a final/undetermined(dead) pair be treated as distinguishible?


Here the pair q0q5 is final/final, but their transition through input 1 is to q2/undefined (dead). Would the undefined be considered be considered nonfinal for the sake of marking the x? Logically it would make sense as it would lead to a nonfinal dead state but i'm not sure

Same for q1q5 through -1-> it goes to q5 which is final DFA


Solution

  • Yes, for the purposes of minimization, the undefined dead state should be treated as nonfinal (it is not an accepting state; strings that lead to it are not in the language of the DFA). As a consequence, pairs consisting of two final (accepting) states are distinct from pairs consisting of one final (accepting) state and the undefined/dead state. To be absolutely sure of this fact, you can add the undefined/dead state in explicitly to get a 7-state DFA where all transitions are defined. Performing minimization on that DFA and then removing any dead state(s) should yield the same DFA as performing the algorithm on your DFA with undefined/dead states, if the convention mentioned earlier is used.

    Note: in a theoretical sense it might be preferable to just list the dead states in DFAs anyway, especially when minimization is being discussed. The number of states in a minimal DFA can be nicely related to the number of equivalence classes under the Myhill-Nerode indistinguishability relation if you follow this convention; if you remove dead states from minimal DFAs this is no longer generally possible, since some minimal DFAs will have dead states and some will not.