• Source: Complementation of automata

In theoretical computer science and formal language theory, the complementation of an automaton is the problem of computing an automaton that accepts precisely the words rejected by another automaton. Formally, given an automaton A which recognizes a regular language L, we want to compute an 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, such as:

Its computational complexity: what is the complexity, given an automaton, of computing an automaton for the complement language?
Its state complexity: what is the smallest number of states of an automaton recognizing the complement?




With deterministic finite automata






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






See also


State complexity




References

Kata Kunci Pencarian:

• Complementation of automata
• Büchi automaton
• Automata theory
• Ω-automaton
• Deterministic pushdown automaton
• Deterministic finite automaton
• Complement (set theory)
• Linear bounded automaton
• Tree automaton
• Context-free language