6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Experts prefer to answer questions if some effort was made by the person asking to expand their knowledge. $\endgroup$ – Vijay D Jul 15 '13 at 9:13
  • $\begingroup$ What do you mean by “complements for an NFA”? Are you talking about constructing a different NFA that recognizes the same language? Or about constructing something else (what?) from an NFA? Or about constructing an NFA that recognizes the complement language? Or something else altogether? $\endgroup$ – Gilles Jul 15 '13 at 10:45
  • $\begingroup$ I've cleaned up the question so hopefully it's more clear, though I am making some assumptions about what is actually being asked. $\endgroup$ – jmite Jul 15 '13 at 17:37
  • 1
    $\begingroup$ Whenever you end up in accept state of NFA just "refuse to accept" else accept? $\endgroup$ – Pratik Deoghare Jul 15 '13 at 20:27
  • 2
    $\begingroup$ 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. $\endgroup$ – vzn Jul 19 '13 at 15:10
6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Pål GD Aug 2 '13 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.