# Complement of Non deterministic Finite Automata

It's known that the complement of a DFA can be easily formed. That is, given a machine $M$, we can construct $M'$ such that $L(M') = \Sigma^* \setminus L(M)$.

Is it possible to construct such a complement for a non-deterministic finite automation (NFA)? To my knowledge, it isn't.

• Experts prefer to answer questions if some effort was made by the person asking to expand their knowledge. Jul 15, 2013 at 9:13
• Whenever you end up in accept state of NFA just "refuse to accept" else accept? Jul 15, 2013 at 20:27
• @PratikDeoghare as Raphael has insinuated in his comment that approach wont work for NFAs. Jul 16, 2013 at 18:41
• @PratikDeoghare The point I was trying to make (which I don't think I did very well) was that the OP is probably not too familiar with NFAs (judging from the question) so your comment may be slightly confusing as a given word doesn't have a unique path through the states of the automaton, it has many paths so simply swapping the accept states for non-accept states and swapping the non-accept states for accept states wont work. Jul 17, 2013 at 11:00
• the question makes more sense if one asks how to complement an NFA without converting it to a DFA, and indeed there seem to be no known algorithms to do this. also, it is true technically that all DFAs are also NFAs (as in the answer), but there is a more strict sense of NFAs in which one can look at the set of NFAs that are not also DFAs.
– vzn
Jul 19, 2013 at 15:10

I'm going to assume that you know that there is an equivalence between DFAs and NFAs in the following sense: For every NFA $M$ there exists a DFA $M'$ such that $L(M') = L(M)$. I'm also going to assume that you know how to, given $M$, calculate $M'$. These are standard methods and they (and their proofs) can be found in any good textbook on automata such as: Hopcroft and Ullman

Given these facts the result is almost immediate: Given an NFA $N$ all you have to do is calculate the corresponding DFA $N'$ and use the complement algorithm which you've mentioned you already know. The resulting DFA is an NFA (since DFAs are just special cases of NFAs) which accepts the complement of the language accepted by the NFA you started with.

So to answer your question, yes it is possible to construct such an NFA, however, if you want to do it quickly you may have some problems

The language represented by an NFA is regular. The complement of a regular language is regular. Every regular language can be represented by an NFA. Hence NFAs can be "complemented".

More concretely, convert your NFA to a DFA and then complement it.

What you're really asking is, probably, is there a more direct way to complement NFAs. There are examples in which there is a large gap between the NFA complexity of a language and its complement. For example, the language of all words over $\{1,\ldots,n\}$ which don't contain all symbols is accepted by an NFA of size $n$ (or $n+1$ if you don't allow multiple starting states), but its complement needs exponentially many states $2^n$.

• Maybe Unni asks: "What happens to the language if you flip accept/non-accept states?" However, the interesting point is, as you already say, whether languages recognized by NFAs are closed under complementation, which you have answered in the positive. Aug 2, 2013 at 12:17