Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
