NFAs and Complements

Finding the complement of a regular language using NFA

The complement of a regular language can be recognized by a machine obtained by inverting the acceptability of each state in a DFA that recognizes the language. The same strategy does not apply, however, to finding the complement of a regular language using a NFA. Why not?

One reason is that NFAs often omit possible moves for input strings, since they represent only what is acceptable in the language. When complementing a language, we are interested in what is not acceptable in the original language, so starting with a NFA won’t work.

Let’s consider the language $L = \{a,bab\}^*$, which the following NFA accepts.