Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Complementation of automata
open-in-new
<p>In <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a> and <a href="/facts/Formal_language_theory/crDTyP8q">formal language theory</a>, the complementation of an <a href="/facts/Finite-state_machine/GMusWd0a">automaton</a>[<i>clarify</i>] is the problem of computing an automaton that accepts precisely the words rejected by another automaton. Formally, given an automaton <i>A</i> which recognizes a <a href="/facts/Regular_language/ahxw67T1">regular language</a> <i>L</i>, we want to compute an automaton that precisely recognizes the words that are not in <i>L</i>, i.e., the <a href="/facts/Complement_(set_theory)/yWUePIYY">complement</a> of <i>L</i>. </p><p>Several questions on the complementation operation are studied, such as: </p> <ul><li>Its <a href="/facts/Computational_complexity/Qenh22Ja">computational complexity</a>: what is the complexity, given an automaton, of computing an automaton for the complement language?</li> <li>Its <a href="/facts/State_complexity/dIaeAN82">state complexity</a>: what is the smallest number of states of an automaton recognizing the complement?</li></ul>