Given a semiautomaton $M=(S,\Sigma,\delta)$ , the transition function is typically defined as a function from $S\times \Sigma$ to $S$ . One may instead think of $\delta$ as a set $C(M)$ of functions $$C(M):=\lbrace \delta_a: S\to S \mid a \in \Sigma \rbrace, \qquad \mbox{where} \qquad \delta_a(s):=\delta(s,a).$$ Since the transition function $\delta$ in $M$ can be extended to the domain $S\times \Sigma^*$ , so can the set $C(M)$ : $$C(M):=\lbrace \delta_u: S\to S\mid u\in \Sigma^*\rbrace,\qquad \mbox{where}\qquad \delta_u(s):=\delta(s,u).$$

The advantage of this interpreation is the following: for any input words $u,v$ over $\Sigma$ : $$\delta_u\circ \delta_v= \delta_{vu},$$ which can be easily verified: $$\delta_{vu}(s)=\delta(s,vu)=\delta(\delta(s,v),u) = \delta(\delta_v(s),u)=\delta_u(\delta_v(s))=(\delta_u\circ \delta_v)(s).$$

In particular, $\delta_{\lambda}$ is the identity function on $S$ , so that the set $C(M)$ becomes a monoid, called the characteristic monoid of $M$ .

The characteristic monoid $C(M)$ of a semiautomaton $M$ is related to the free monoid $\Sigma^*$ generated by $\Sigma$ in the following manner: define a binary relation $\sim$ on $\Sigma^*$ by $u\sim v$ iff $\delta_u = \delta_v$ . Then $\sim$ is clearly an equivalence relation on $\Sigma^*$ . It is also a congruence relation with respect to concatenation: if $u\sim v$ , then for any $w$ over $\Sigma$ : $$\delta_{uw}(s)=\delta_u(\delta_w(s))=\delta_v(\delta_w(s))=\delta_{vw}(s)$$ and $$\delta_{wu}(s)=\delta_w(\delta_u(s))=\delta_w(\delta_v(s))=\delta_{wv}(s).$$ Putting the two together, we see that if $x\sim y$ , then $ux \sim vx \sim vy$ . We denote $[u]$ the congruence class in $\Sigma^*/\sim$ containing the word $u$ .

Now, define a map $\phi: C(M)\to \Sigma^*/\sim$ by setting $\phi(\delta_u)=[u]$ . Then $\phi$ is well-defined. Furthermore, under $\phi$ , it is easy to see that $C(M)$ is anti-isomorphic to $\Sigma^*/\sim$ .

Remark. In order to avoid using anti-isomorphisms, the usual practice is to introduce a multiplication $\cdot$ on $C(M)$ so that $\delta_u \cdot \delta_v:=\delta_v \circ \delta_u$ . Then $C(M)$ under $\cdot$ is isomorphic to $\Sigma^*/\sim$ .

Some properties:

• If $M$ and $N$ are isomorphic semiautomata with identical input alphabet, then $C(M)=C(N)$ .
• If $N$ is a subsemiautomaton of $M$ , then $C(N)$ is a homomorphic image of a submonoid of $C(M)$ .
• If $N$ is a homomorphic image of $M$ , so is $C(N)$ a homomorphic image of $C(M)$ .

Bibliography

1

A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).

2

M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).