Finding the complement of a DFA structure

Question

So I'm working on a method that converts a dfa to it's complement. The complement rejects all strings the dfa accepts, and accepts all strings thee dfa rejects. To do this I am supposed to follow this algorithm: "First add an explicit dead state and make explicit all transitions to it. Second change all final states to non-final states, and all non-final states to final states."

I took a shot at this, and had no success. I don't think I understand correctly.

First I changed all the final states to non final states and non final states to final states.

Then for each state, if it didn't have a transition with an alphabet, I added a transition from that state to the explicit dead state, using those alphabets

Is this correct?

You seem to have inverted the meaning of the words "first" and "second" in the algorithm. I suggest you try it again, using the more conventional definitions of those words. — rici
@rici If I add the dead state first, I then have to iterate over all the states and change final to nonfinal and vice versa. Since the dead state wouldn't be final, would it be changed to final? or kept dead? — Jake Senior
That's correct. The "dead" state as created is non-final, and the second step will change it to final. It will still have itself as the target of every transition, so once entered, it cannot be left. More like a black hole than a zombie :) — rici

kraskevich kraskevich · Accepted Answer · 2015-03-06T20:09:48

No, you should first a transition to a newly created dead state for all states and symbols such that there is no transition from a specific state by a specific symbol and after that you should make all final states non-final and vice versa. The dead state becomes final when we do it in this order, and that's exactly what should happen(if we reach the dead state, the given string is not accepted by the original automaton. Thus, it should be accepted by its complement).

Finding the complement of a DFA structure

1 Answers