Complement Operation on Automata

I wonder why nowhere on the net is found that mention the requirements of the complement operation on automata or precisely define this operation.

In fact complement operation is only defined on deterministic automata. Applying it to NFAs will result to strange things. For example, consider the following automata:

You might think that its complement is the following automaton:

But it isn’t. The automaton above accepts both h and the empty string.

Another important thing about DFAs before applying the complement operation is to add a halt or sink state.

Thus for the following automaton:

The complement is as follows:

You should note that the complement of an automaton that accepts h doesn’t mean an automaton that accepts everything other than h. If fact the complement of an automaton with language L and alphabet ∑ is an automaton that accepts ∑* – L. So complementing an automaton that accepts h with alphabet {h} is an automaton that accepts h* except the string containing a single h. Therefore the complement automaton accepts h* – h = {λ,hh,hhh,hhhh,…}.

I hope it was useful ;)