complementation of automata
{{Short description|Concept in theoretical computer science}}
In theoretical computer science and formal language theory, the complementation of an {{clarify span|automaton|reason=If this article is intended to deal only with finite automata, this should be reflected in the text here, and in the title. On the other hand, if it is intended to be more general (including automata with e.g. stack(s) or tape(s), the link underlying 'automaton' should be changed appropriately.|date=December 2023}} 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
{{expand section|date=December 2023}}
With nondeterministic finite automata
With a nondeterministic finite automaton, the state complexity of the complement automaton may be exponential.{{cite journal|last1=Birget|first1=Jean-Camille|title=Partial orders on words, minimal elements of regular languages, and state complexity|journal=Theoretical Computer Science|volume=119|issue=2|year=1993|pages=267–291|issn=0304-3975|doi=10.1016/0304-3975(93)90160-U}} Lower bounds are also known in the case of unambiguous automata.{{cite arXiv |last1=Göös |first1=Mika |last2=Kiefer |first2=Stefan |last3=Yuan |first3=Weiqiang |title=Lower Bounds for Unambiguous Automata via Communication Complexity |date=12 February 2022 |class=cs.FL |eprint=2109.09155}}
With two-way automata
Complementation has also been studied for two-way automata.{{Cite journal |last1=Geffert |first1=Viliam |last2=Mereghetti |first2=Carlo |last3=Pighizzini |first3=Giovanni |date=2007-08-01 |title=Complementing two-way finite automata |journal=Information and Computation |volume=205 |issue=8 |pages=1173–1187 |doi=10.1016/j.ic.2007.01.008 |issn=0890-5401|doi-access=free }}
With Büchi automata
{{Main|Complementation of Büchi automaton}}