0 | 1 | |
---|---|---|
->A | B | A |
B | C | D |
*C | F | E |
D | E | A |
E | F | D |
*F | F | B |
Find a minimal equivalent DFA. Show your work, i.e., the results of the rounds in which you discover new, distinguishable pairs of states.
Requirements: You should read the construction for intersection in the course reader. The construction for symmetric difference is similar. You should modify this construction, rather than, say, expressing symmetric difference in terms of other operations that we know preserve regularity. Also, remember that you need not only to give a construction, but to prove that your construction is correct. Your proof should begin with the omitted induction on the length of w that is mentioned at the bottom of p. 117 of the course reader, showing that the product automaton really does simulate the automata for L and M. The ideas of the proof are not hard, but remember to state the important points, including arguments in both directions for the if-and-only-if. You also need to provide the clincher, that the accepting states of the product automaton have been correctly selected by you.