Complementation of automata

In theoretical computer science and formal language theory, complementation is a computational problem that applies to automata. An automaton is an abstract machine that verifies a property on its inputs, and either accepts it (if the property is verified) or rejects it (if the property is not verified). The complement of an automaton is another automaton that accepts precisely what the other one rejects, and vice-versa. More precisely, an automaton A defines a formal language L formed of the inputs that A accepts, and complementation is the problem of computing a "complement" automaton that precisely recognizes the words that are not in L, i.e., the complement of L.

Several questions on the complementation operation are studied in automata theory research, such as:

With deterministic finite automata

A complete deterministic finite automation can be complemented by switching its accepting and non-accepting states while leaving its transitions and initial state unchanged. The resulting automaton accepts exactly those input strings that the original automation rejects.

With nondeterministic finite automata

With a nondeterministic finite automaton, the state complexity of the complement automaton may be exponential. Lower bounds are also known in the case of unambiguous automata.

With two-way automata

Complementation has also been studied for two-way automata.

With Büchi automata