Semiautomaton

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.
Associated with any semiautomaton is a monoid called the characteristic monoid, input monoid, transition monoid or transition system of the semiautomaton, which acts on the set of states "Q". 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) "S"-acts are called "operands".
Transformation semigroups and monoid acts.
A transformation semigroup or transformation monoid is a pair formula_1 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. They are functions in the sense that every element "m" of "M" is a map formula_2. If "s" and "t" are two functions of the transformation semigroup, their semigroup product is defined as their function composition formula_3.
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.
"M"-acts.
Let "M" be a monoid and "Q" be a non-empty set. If there exists a multiplicative operation
which satisfies the properties
for 1 the unit of the monoid, and 
for all formula_8 and formula_9, then the triple formula_10 is called a right "M"-act or simply a right act. In long-hand, formula_11 is the "right multiplication of elements of Q by elements of M". The right act is often written as formula_12.
A left act is defined similarly, with
and is often denoted as formula_15.
An "M"-act is closely related to a transformation monoid. However the elements of "M" need not be functions "per se", they are just elements of some monoid. Therefore, one must demand that the action of formula_11 be consistent with multiplication in the monoid ("i.e." formula_17), as, in general, this might not hold for some arbitrary formula_11, in the way that it does for function composition.
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. In particular, this allows elements of the monoid to be represented as strings of letters, in the computer-science sense of the word "string". 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.
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.
"M"-homomorphism.
For two "M"-acts formula_12 and formula_20 sharing the same monoid formula_21, an "M"-homomorphism formula_22 is a map formula_23 such that
for all formula_25 and formula_26. The set of all "M"-homomorphisms is commonly written as formula_27 or formula_28.
The "M"-acts and "M"-homomorphisms together form a category called "M"-Act.
Semiautomata.
A semiautomaton is a triple formula_29 where formula_30 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 formula_32, but without the initial state formula_33 or set of accept states "A". Alternately, it is a finite state machine that has no output, and only an input.
Any semiautomaton induces an act of a monoid in the following way.
Let formula_34 be the free monoid generated by the alphabet formula_30 (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 formula_30.
For every word "w" in formula_34, let formula_38 be the function, defined recursively, as follows, for all "q" in "Q":
Let formula_49 be the set
The set formula_49 is closed under function composition; that is, for all formula_52, one has formula_53. It also contains formula_54, which is the identity function on "Q". Since function composition is associative, the set formula_49 is a monoid: it is called the input monoid, characteristic monoid, characteristic semigroup or transition monoid of the semiautomaton formula_29.
Properties.
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 formula_57, and individual states are referred to as "n"-state qubits. State transitions are given by unitary "n"×"n" matrices. The input alphabet formula_30 remains finite, and other typical concerns of automata theory remain in play. Thus, the quantum semiautomaton may be simply defined as the triple formula_59 when the alphabet formula_30 has "p" letters, so that there is one unitary matrix formula_61 for each letter formula_46. Stated in this way, the quantum semiautomaton has many geometrical generalizations. Thus, for example, one may take a Riemannian symmetric space in place of formula_57, 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.