In automata theory

Automata theory

In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...

, automata construction is an important mathematical technique used to demonstrate the existence of an automaton with a certain desired property. Very often, it is presented as an algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 that takes a desired property as input and produces as output an automaton with the property.

Many hard problems in automata theory involve finding the right construction of an automaton such that the problem can be answered. For example, the famous construction in McNaughton's Theorem

McNaughton's Theorem

In automata theory, McNaughton's theorem refers to a theorem that asserts that the set of ω-regular languages is identical to the set of languages recognizable by deterministic Muller automata....

 answered the question if non-deterministic Büchi automaton

Büchi automaton

In computer science and automata theory, a Büchi automaton is a type of ω-automaton, which extends a finite automaton to infinite inputs. It accepts an infinite input sequence iff there exists a run of the automaton that visits one of the final states infinitely often. Büchi automata recognize the...

 can always be translated into a deterministic Muller automaton

Muller automaton

In automata theory, a Muller automaton is a type of an ω-automaton.The acceptance condition separates a Muller automomaton from other ω-automata....

.

Example

Powerset construction

Powerset construction

In the theory of computation and Automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton into a deterministic finite automaton which recognizes the same formal language...

 is an algorithm to construct a deterministic finite automaton from a given nondeterministic finite automaton.

Optimality of a construction

An automata construction is called optimal if there is an input to the construction such that there exist no automaton that satisfy the desired property with smaller size complexity than output of the construction.