Can reversing the final and non-final states of a DFA produce the complement of the original language?

Problem Detail: 

Is this true? If I change all final states of a given Deterministic Finite Automata to non final states and all non final states to final states then does this new automata represent the complement of the language that was accepted by the original automata?

What if we talk about a Non deterministic finite automata instead of a DFA?

Asked By : bigbong

Answered By : Ron Teller

In DFAs, the path taken in the automaton are deterministic and reach one specific state, so all the strings in the language reach one accepted state and all the other strings on this alphabet reach non-accepting states. Switching the accepting and non-accepting path is equivalent to saying "accept every string that doesn't reach an accepting state in the original automaton, don't accept any string that reach an accepting state in the original automaton", in short, "Not in the language L of the original automaton", which is the complement of L.

In NFAs, it is quite easy to find contradiction to show that this statement is incorrect.

Consider the following 2-state NFA with the alphabet {a, b}:

state 1 (starting state, accepting state):   input a -> go to state 1   input b -> go to state 2  state 2:   input a -> go to state 1 and 2   input b -> go to state 2 

The string "aaba" is accepted by this automaton. If we switch the accepting states, this string is still accepted by the automaton, and thus the two languages can't be the complement of each other.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21359