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 [...]