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) semigroup actions are called "operands".
In category theory, semiautomata essentially are functors.
See main article: semigroup action.
A transformation semigroup or transformation monoid is a pair
(M,Q)
m\colonQ\toQ
(st)(q)=(s\circt)(q)=s(t(q))
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.
Let M be a monoid and Q be a non-empty set. If there exists a multiplicative operation
\mu\colonQ x M\toQ
(q,m)\mapstoqm=\mu(q,m)
which satisfies the properties
q1=q
for 1 the unit of the monoid, and
q(st)=(qs)t
for all
q\inQ
s,t\inM
(Q,M,\mu)
\mu
QM
A left act is defined similarly, with
\mu\colonM x Q\toQ
(m,q)\mapstomq=\mu(m,q)
and is often denoted as
MQ
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
\mu
\mu(q,st)=\mu(\mu(q,s),t)
\mu
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.
For two M-acts
QM
BM
M
f\colonQM\toBM
f\colonQ\toB
f(qm)=f(q)m
for all
q\inQM
m\inM
Hom(QM,BM)
HomM(Q,B)
The M-acts and M-homomorphisms together form a category called M-Act.[1]
A semiautomaton is a triple
(Q,\Sigma,T)
\Sigma
T\colonQ x \Sigma\toQ.
(Q,\Sigma,T,q0,A)
q0
Any semiautomaton induces an act of a monoid in the following way.
Let
\Sigma*
\Sigma
\Sigma
For every word w in
\Sigma*
Tw\colonQ\toQ
w=\varepsilon
T\varepsilon(q)=q
\varepsilon
w=\sigma
\Sigma
T\sigma(q)=T(q,\sigma)
w=\sigmav
\sigma\in\Sigma
v\in\Sigma*
Tw(q)=Tv(T\sigma(q))
Let
M(Q,\Sigma,T)
M(Q,\Sigma,T)=\{Tw\vertw\in\Sigma*\}.
The set
M(Q,\Sigma,T)
v,w\in\Sigma*
Tw\circTv=Tvw
T\varepsilon
M(Q,\Sigma,T)
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.
CPn
\Sigma
n,\Sigma,\{U | |
(CP | |
\sigma1 |
,U | |
\sigma2 |
,...c,U | |
\sigmap |
\})
\Sigma
U\sigma
\sigma\in\Sigma
CPn
The syntactic monoid of a regular language is isomorphic to the transition monoid of the minimal automaton accepting the language.