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?
Can reversing the final and non-final states of a DFA produce the complement of the original language?
formal languages;automata;finite automata
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 2state 2:  input a -> go to state 1 and 2  input b -> go to state 2The 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.