In mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton having inputs but no output.
It consists of a set Q of states, a set Σ called the input alphabet, and a function T: Q × Σ → Q called the transition function.
This may be viewed either as an action of the free monoid of strings in the input alphabet Σ, or as the induced transformation semigroup of Q.
In older books like Clifford and Preston (1967) semigroup actions are called "operands".
In category theory, semiautomata essentially are functors.
consisting of a set Q (often called the "set of states") and a semigroup or monoid M of functions, or "transformations", mapping Q to itself.
Some authors regard "semigroup" and "monoid" as synonyms.
Here a semigroup need not have an identity element; a monoid is a semigroup with an identity element (also called "unit").
Since the notion of functions acting on a set always includes the notion of an identity function, which when applied to the set does nothing, a transformation semigroup can be made into a monoid by adding the identity function.
If there exists a multiplicative operation which satisfies the properties for 1 the unit of the monoid, and for all
is called a right M-act or simply a right act.
A left act is defined similarly, with and is often denoted as
An M-act is closely related to a transformation monoid.
Once one makes this demand, it is completely safe to drop all parenthesis, as the monoid product and the action of the monoid on the set are completely associative.
This abstraction then allows one to talk about string operations in general, and eventually leads to the concept of formal languages as being composed of strings of letters.
[further explanation needed] Another difference between an M-act and a transformation monoid is that for an M-act Q, two distinct elements of the monoid may determine the same transformation of Q.
If we demand that this does not happen, then an M-act is essentially the same as a transformation monoid.
is a non-empty set, called the input alphabet, Q is a non-empty set, called the set of states, and T is the transition function When the set of states Q is a finite set—it need not be—, a semiautomaton may be thought of as a deterministic finite automaton
or set of accept states A. Alternately, it is a finite-state machine that has no output, and only an input.
(so that the superscript * is understood to be the Kleene star); it is the set of all finite-length strings composed of the letters in
If the set of states Q is finite, then the transition functions are commonly represented as state transition tables.
The structure of all possible transitions driven by strings in the free monoid has a graphical depiction as a de Bruijn graph.
The set of states Q need not be finite, or even countable.
As an example, semiautomata underpin the concept of quantum finite automata.
There, the set of states Q are given by the complex projective space
, and individual states are referred to as n-state qubits.
Thus, the quantum semiautomaton may be simply defined as the triple
Stated in this way, the quantum semiautomaton has many geometrical generalizations.
, and selections from its group of isometries as transition functions.
The syntactic monoid of a regular language is isomorphic to the transition monoid of the minimal automaton accepting the language.