Why can we not directly complement an NFA
I know that it is possible to build the complement of a DFA by simply making final states rejecting states and by making rejecting states final states. However, if I have given an NFA we cannot directly swap the states and it will be its complement. This construction will fail and hence we have to translate the NFA to a DFA before doing so. Could someone give me an explanation why this is?
$\endgroup$ 31 Answer
$\begingroup$First of all, you have to use a complete deterministic automaton for this algorithm to work. It already fails otherwise. Take for instance the one-state automaton ${\cal A} =(Q, A, E, 1, F)$ where $A = \{a,b\}$, $Q = F = \{1\}$ and $E = \{(1,a,1)\}$. In other words, $1 \xrightarrow{a} 1$ is the unique transition in $\cal A$. Then $L(\cal A) = a^*$, and the complement of this language is equal to $A^*bA^*$. Now if you swap the final states in $\cal A$, you obtain an automaton without any final state, which accepts the empty language.
$\endgroup$
