Just like groups and rings, a semiautomaton can be viewed as an algebraic structure. As such, one may define algebraic constructs such as subalgebras and homomorphisms. In this entry, we will briefly discuss the later.

Definition

A homomorphism from a semiautomaton $M=(S,\Sigma,\delta)$ to a semiautomaton $N=(T,\Gamma,\gamma)$ is a pair of maps $h:=(f:S\to T,g:\Sigma \to \Gamma)$ such that $$f(\delta(s,a))= \gamma(f(s),g(a))$$ The image of the homomorphism $h$ is the subsemiautomaton $h(M):=(f(S),g(\Sigma),\gamma')$ of $N$ , where $\gamma'$ is the restriction of $\gamma$ to $f(S)\times g(\Sigma)$ , also known as the homomorphic image of $M$ under $h$ .

In general, a semiautomaton $N$ is said to be a homomorphic image of a semiautomaton $M$ , if there is a homomorphism $h$ such that $h(M)=N$ .

When comparing two semiautomata $M,N$ , it is customary to identify the two corresponding input alphabets $\Sigma, \Gamma$ , especially when one wants to study the interaction between the states of $M$ and the states of $N$ . This can be done by taking $\Delta:=\Sigma\cup \Gamma$ , and extend the corresponding transition functions so that they are identities on the extended portions of the input alphabets. Call the extended semiautomata $M',N'$ .

If $h:M\to N$ is a homomorphism, then $h':M'\to N'$ extends $h$ in a natural way: $f'=f$ , and $g':\Delta \to \Delta$ given by $g'(a)=g(a)$ if $a\in \Sigma$ , and $g'(a)=a$ if $a\in \Gamma-\Sigma$ . Routine verification shows that $h'$ is indeed a homomorphism: if $a\in \Sigma$ , $$f'(\delta'(s,a))=f(\delta'(s,a))=f(\delta(s,a))=\gamma(f(s),g(a))=\gamma'(f(s),g(a))=\gamma'(f'(s),g'(a)),$$ and if $a\in \Gamma-\Sigma$ , then $$f'(\delta'(s,a))=f(\delta'(s,a))=f(s)=\gamma'(f(s),a)=\gamma'(f'(s),a)=\gamma'(f'(s),g'(a)).$$

A homomorphism $h=(f,g):M\to N$ is an isomorphism if both $f$ and $g$ are bijections. As discussed above, if we identify the input alphabets of $M$ and $N$ , and treat $g$ as the identity map on the input alphabet, then $(S,\Sigma,\delta)$ and $(T,\Sigma,\gamma)$ are isomorphic if there is a bijection $f:S\to T$ such that $f(\delta(s,a))=\gamma(f(s),a)$ .

Specializations to Other Machines

Computing devices derived from semiautomata such as automata and state-output machines may also be considered as algebras. We record the definitions of homomorphisms with respect to these objects here.

We adopt the following notations: given an automaton $A=(S,\Sigma,\delta,I,F)$ and a state-output machine $M=(S,\Sigma,\Delta,\delta,\lambda)$ , let $A'$ and $M'$ be the associated semiautomaton $(S,\Sigma,\delta)$ . So $A$ and $M$ may be written $(A',I,F)$ and $(M',\Delta,\lambda)$ respectively.

Definition (automaton). Given automata $A=(A',I,F)$ and $B=(B',J,G)$ . Then $$h=(f,g):A\to B$$ is a homomorphism if

• $h:A'\to B'$ is a semiautomaton homomorphism, such that
• $f(I)\subseteq J$ , and $f(F)\subseteq G$ .

Definition (state-output machine). Given state-output machines $M=(M',\Delta,\lambda)$ and $N=(N',\Omega,\pi)$ . Then $$\phi=(h,k): M\to N$$ is a homomorphism if

• $h:M'\to N'$ is a semiautomaton homomorphism, and
• $k:\Delta \to \Omega$ , such that $$k(\lambda(s,a))=\pi(f(s),g(a)),$$ for all $(s,a)\in S\times \Sigma$ , where $S$ and $\Sigma$ are the state and input alphabets of $M$ .

Bibliography

1

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