In
theoretical computer science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
and
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
, the complementation of an 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
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
''L'', we want to compute an automaton recognizing precisely the words that are not in ''L'', i.e., the
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-clas ...
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 State complexity is an area of theoretical computer science
dealing with the size of abstract automata,
such as different kinds of finite automata.
The classical result in the area is that
simulating an n-state
nondeterministic finite automaton
by ...
: 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
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state ...
, the
state complexity State complexity is an area of theoretical computer science
dealing with the size of abstract automata,
such as different kinds of finite automata.
The classical result in the area is that
simulating an n-state
nondeterministic finite automaton
by ...
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 State complexity is an area of theoretical computer science
dealing with the size of abstract automata,
such as different kinds of finite automata.
The classical result in the area is that
simulating an n-state
nondeterministic finite automaton
by ...
References
Automata (computation)
{{improve categories, date=December 2023