数理解析研究所講究録 1222 巻 2001 年 53-57

53
Characterization of finite Automata by the Images andthe Kernels of their Transition Functions 1
T. Saito (斎藤 立彦)
Mukunoura 374, Innoshima,
Hiroshima, Japan, 722-23221
e-mail:tatsusaito@mx4.tiki.ne.jp
1. Introduction
By an automaton $A$, we mean here a3-tuple $(X,A, \delta)$ , where $X$ is afinite
set (the set of states), is afinite alphabet (the set of inputs) and is amapping of $X\cross A$ into $X$ (the transition function).
As usual,anddenotes the ffee monoid and free semigroup gener$A$
ated by , respectively, and is extended from $X\cross A$ to. In thiscase,is denoted simply by $xs$ for $x\in X$ , $s\in A^{*}$
Let $\rho=$ { $(s,t)$: $xs=xt$ for every $x\in X$ }. Then is acongruence on
andis afinite transformation semigroup on $X$ by
defining the action of
on $X$ as $x(s\rho)=xs$ . The semigroupiscalled the characteristic semigroup of $A$. Let be aclass of semigroups notnecessarily avariety. Then an automaton $A$ is called a -type if.
For $s\in A^{*}$ , let $\mathrm{i}\mathrm{m}s=\{xs:x\in X\}=Xs$ and:$xs=ys\}$ , which are called the image and the kernel of , respectively. Thenis an equivalence on $X$ .
Let)andbe two classes of semigroups. Then the direct product ofandis defined by $\mathcal{V}\cross \mathcal{U}=\{V\cross U : V\in \mathcal{V}, U\in Il\}$ . Let
and let be asemigroup. If for each $s\in V$ , there exists
such that$S=\mathrm{u}\{U_{s} : s\in U\}$ and, then we saythat belongs to, where denotes adisjoint union..
As our start, we consider the following classes of semigroups:,{right zero semigroups $[st$ $=t]$ }{left zero semigroups $[st$ $=s]$ },and. We first characterize, for the classes(;,
and, their types automata by the images
and the kernels of their transition functions. By using the results, we characterize, forand,-type automaton by the same way.
$A$$\delta$$A^{+}$$A^{*}$$X\cross A^{*}$$\delta$$\delta(x, s)$$\in A^{*}\cross A^{*}$$\rho$$A^{*}$$A^{*}/\rho$$s\rho\in A^{*}/\rho$$A^{*}/\rho$$\mathcal{V}$$A^{+}/\rho\in \mathcal{V}$$\mathcal{V}$$\mathrm{k}\mathrm{e}\mathrm{r}s=\{(x,y)\in X\cross X$$s$$\mathrm{k}\mathrm{e}\mathrm{r}s$$\mathcal{U}$$\mathcal{V}$$\mathcal{U}$$U\in \mathcal{U}$$S$$U_{s}\in \mathcal{U}$$U_{s}\cdot$$S$$U_{t}=\{u_{s}u_{t} :v_{s}\in U_{s}, v_{t}\in U_{t}\}\subseteq U_{st}$$\mathrm{U}$$\mathcal{V}(\mathcal{U})$$\mathcal{G}=\{\mathrm{g}\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{p}\mathrm{s}\}$$\mathcal{L}Z=$$\mathcal{R}Z=$$S\mathcal{L}=\{\mathrm{s}\mathrm{e}\mathrm{m}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{i}\mathrm{c}\mathrm{e}\mathrm{s}[st =ts, s^{2}=s]\}$$\mathcal{L}Z\cross \mathcal{G},(;\cross \mathcal{R}Z$$\mathcal{L}Z\cross Ci$$\mathcal{V}\in\{\mathrm{S}\mathrm{C}, \mathcal{L}Z,\mathcal{R}Z\}$$\cross \mathcal{R}Z$$\mathcal{U}\in\{\mathcal{G}, \mathcal{L}Z\cross \mathcal{G}, \mathcal{G}\cross\prime \mathcal{R}Z, \mathcal{L}Z\cross Ci\cross \mathcal{R}Z\}$$\mathcal{V}(\mathcal{U})$1 This is an

abstract and the details will be published eleswher

54
For aexample, we show later that an automaton A is a $SC(CZ$ x
if and only if im st im
for every s, t cE A”.
$\ovalbox{\tt\small REJECT}$$(\ovalbox{\tt\small REJECT})$-type$sf^{\ovalbox{\tt\small REJECT}}I\mathrm{i}\mathrm{m}t$2. Preliminaries
For aset ,denotes the cardinality of , for an equivalence ,denotes the A-class containing anddenotes the number of A-classes.
$s\inA^{+}$, and fori.e.,,denotes the length of . Then$s\inA^{+}$
clearly
for every.
For $s\in A^{*}$ , let fix $s=\{x\in X : xs=x\}$ . Let $E(A^{+})=\{e\in A^{+}:$ $(e, e^{2})\in$. Then it is easy to see that $e\in E(A^{+})$ if and only if. and$(e,f)\in\rho$$f\in
E(A^{+})$
that
for ,
if and only if
and
.
$s\in
A^{+}$, there exists apositive integer $m$ suchis finite, for every
Since
that $s^{m}\in E(A^{+})$ .
$\mathrm{Y}$$\mathrm{Y}$$|\mathrm{Y}|$$x$$|\lambda|=|\{x\mathrm{A} :$x\lambda$$\lambda$$|\lambda|$x\in X\}|$

$|s|$

$s$

$|\mathrm{i}\mathrm{m}s|=|\mathrm{k}\mathrm{e}\mathrm{r}s|$$\mathrm{i}\mathrm{m}e=\mathrm{f}\mathrm{i}\mathrm{x}$$\rho\}$$e$$\mathrm{i}\mathrm{m}e=\mathrm{i}\mathrm{m}f$$e$$\mathrm{k}\mathrm{e}\mathrm{r}e=\mathrm{k}\mathrm{e}\mathrm{r}f$$A^{+}/\rho$Lemma 1. Let $s,t\in A^{+}$ . Then
(1) If.
then, then(2) If.
Lemma 2. Let $s\in A^{+}$ . Then the following are equivalent:(1)
for every $x\in X$ .
(2)
and
.
for every(3) there exists $e\in E(A^{+})$ such thatand ( es)\in \rho .
Lemma 3. The following are equivalent:
For every $s,t\in A^{+}$ ,(1)
for every $x\in X$ ,(2).
$\mathrm{i}\mathrm{m}st=\mathrm{i}\mathrm{m}t$$|\mathrm{k}\mathrm{e}\mathrm{r}st|=|\mathrm{k}\mathrm{e}\mathrm{r}t|_{f}$$|\mathrm{i}\mathrm{m}st|$$\mathrm{k}\mathrm{e}\mathrm{r}st=\mathrm{k}\mathrm{e}\mathrm{r}s$$=|\mathrm{i}\mathrm{m}s|$$\mathrm{i}\mathrm{m}s\cap x\mathrm{k}\mathrm{e}\mathrm{r}$$s\neq\emptyset$$\mathrm{i}\mathrm{m}s^{m}=\mathrm{i}\mathrm{m}s$$m\in \mathrm{N}^{+}$$\mathrm{k}\mathrm{e}\mathrm{r}s^{m}=\mathrm{k}\mathrm{e}\mathrm{r}s$$\mathrm{i}\mathrm{m}s=\mathrm{i}\mathrm{m}e,\mathrm{k}\mathrm{e}\mathrm{r}s=\mathrm{k}\mathrm{e}\mathrm{r}e$, ( se)\in \rho
$s,$

$s,$

$\mathrm{i}\mathrm{m}s\cap x\mathrm{k}\mathrm{e}\mathrm{r}$$t\neq\emptyset$$\mathrm{i}\mathrm{m}st=\mathrm{i}\mathrm{m}t$(3)$\mathrm{k}\mathrm{e}\mathrm{r}st=\mathrm{k}\mathrm{e}\mathrm{r}s$.

Let $A=(X,A,\delta)$ be an automaton, and let. Then we haveandand
. In fact, if $s\in A^{+}$ , then $s=s’a=6s$ ”for some$a,b\in A$ , $s’s”\in A^{*}$ , so thatand.
for every $s\in A^{+}$ , the restriction
Since
of to
can be. Then the automaton
defined. Letiscffied the subautomaton of $A$ with respect to Y.
Let $s,t\in A^{+}$ and $x\in X$ . Since
the action of sty on $X$ isdefined by$\mathrm{Y}=\mathrm{U}\{\mathrm{i}\mathrm{m}a :$\kappa=\cap\{\mathrm{k}\mathrm{e}\mathrm{r}a :$\kappa=\cap\{\mathrm{k}\mathrm{e}\mathrm{r}s :a\in A\}$$\mathrm{Y}=\mathrm{U}\{\mathrm{i}\mathrm{m}s;s\in A^{+}\}$

s\in A^{+}\}$$\mathrm{i}\mathrm{m}s’a\subseteq \mathrm{i}\mathrm{m}$$a$$\mathrm{k}\mathrm{e}\mathrm{r}b\subseteq \mathrm{k}\mathrm{e}\mathrm{r}6\mathrm{s}"$$\mathrm{Y}s\subseteq \mathrm{Y}$$A_{\mathrm{Y}}=\{a_{\mathrm{Y}} :$s_{\mathrm{Y}}$a\in A\}$$=\mathrm{x}(\mathrm{s}\mathrm{t})$$s$$\mathrm{Y}$$A_{\mathrm{Y}}=(\mathrm{Y},A_{\mathrm{Y}}, \delta)$$(xs)t_{\mathrm{Y}}=(\mathrm{x}\mathrm{s})\mathrm{t}\mathrm{j}$$x(st_{\mathrm{Y}})$a\in A\}$

55
Let be as above. Define the action of $s\in A^{+}$ on
by $(x\kappa)s=(xs)\kappa$ .
Then the action is well-defined. In fact, if, then $(x,y)\in\kappa$,, is denoted by . Let
so that $xs=ys$ . When the action of is on. Then the automaton
is cffied theautomaton induced from $A$ by .
Let $s,t\in A^{+}$ and $x\in X$ . Then clearly (xker ) $s=xs$ . Since,
we have $(x\kappa)s=xs$ , so that $((x\kappa)s_{\kappa})t=((xs)\kappa)t=(xs)t$ , Thus the actionof $sKt$ on $X$ is defined by $x(s_{\kappa}t)=x(st)$ .
$X/\kappa$$\kappa$$x\kappa$

a\in a\}$$\subseteq \mathrm{k}\mathrm{e}\mathrm{r}s$$X/\kappa$$s$$A_{\kappa}=\{a_{\kappa} :$=y\kappa$$s$$s_{\kappa}$$A_{\kappa}=(X/\kappa,A_{\kappa},\delta)$$\kappa$$s$$\kappa$$\subseteq \mathrm{k}\mathrm{e}\mathrm{r}s$

For an automaton $A=(X, A,\delta)$ , let:$i\in I\}$ , i.e., for each $i\in I$ , Y4
for some $s\in A^{+}$ andfor every $s\in A^{+}$ , and let,
and: $s\in$(xker$A^{+}\}=\{\kappa_{\mu} : \mu\in M’\}$ . In this case, ifholds for every $s\in A^{+}$
and $x\in X$ , then $Im(A^{+})=Im(E(A^{+}))$ and $Ker(A^{+})=Ker(E(A^{+}))$ .
$Im(A^{+})=\{\mathrm{i}\mathrm{m}s:s\in A^{+}\}=\{\mathrm{Y}_{\dot{l}}$$=\mathrm{i}\mathrm{m}s$$\mathrm{i}\mathrm{m}s\in Im(A^{+})$$Ker(A^{+})=\{\mathrm{k}\mathrm{e}\mathrm{r}s :$Im(A_{\kappa}^{+})=\{\mathrm{i}\mathrm{m}s_{\kappa} :s\in A^{+}\}=\{Z\dot{.} :i\in I’\}$s\in A^{+}\}=\{\kappa_{\mu} :\mu\in \mathrm{A}\mathrm{t}\}$$Ker(A_{\mathrm{Y}}^{+})=\{\mathrm{k}\mathrm{e}\mathrm{r}s_{\mathrm{Y}}$$s\neq\emptyset$$\mathrm{i}\mathrm{m}$3. Main Results
Asemigroup in CZ
by$\mathcal{L}\mathcal{G}$, i.e.,

is cffied a left group whose class is denoted simply$\cross Ci$$\mathcal{L}\mathcal{G}=\mathcal{L}Z\cross \mathcal{G}$.

Theorem 1. Let $A=(X, A, \delta)$ be an automaton. Then the following are
equivalent :(1) There exists a subset of $X$ such that
and
$a\in
A$
$x\in
X$
and
.
for every(2) There exists a subset Y of X such that ims
for every s $\in S$ .
(3) A is a left group type.
$\mathrm{i}\mathrm{m}a=\mathrm{Y}$$\mathrm{Y}$$\mathrm{Y}\cap x\mathrm{k}\mathrm{e}\mathrm{r}$$a\neq\emptyset$$=\mathrm{Y}$Prom Theorem 1we obtain the folowing results
Corollary 1.1. An automaton $A=(X, A, \delta)$ is a
if
for every , $t\in A^{+}$ .
$\mathrm{i}\mathrm{m}st=\mathrm{i}\mathrm{m}s\cap \mathrm{i}\mathrm{m}t$$\mathrm{i}\mathrm{m}st=\mathrm{i}\mathrm{m}t$$\mathcal{R}\mathcal{G}$-type if and only$a\mathcal{R}Z(\mathcal{L}\mathcal{G})$-type if and only$s$

Corollary 1.2. An automaton $A=(X,A, \delta)$ is
iffor every , $t\in A^{+}$ .

Asemigroup in (;, i.e.,$S\mathcal{L}(\mathcal{L}\mathcal{G})$$s$$\cross \mathcal{R}Z$$\mathcal{R}\mathcal{G}=\mathcal{G}\cross \mathcal{R}Z$.

is called aright group whose class is denoted by

Theorem 2. Let A $=(X,$A,
equivalent :$\delta)$be an automaton. Then the following are56(1) There$\emptyset$$e$$\dot{m}ts$

for every $a\in A$ .
(2) There

an equivalence on $X$ such that$\kappa$$e$ $\dot{m}ts$

an equivalence.
(3) A is a right group type.

$\kappa$and$\mathrm{k}\mathrm{e}\mathrm{r}a=\kappa$

on $X$ such that$\mathrm{i}\mathrm{m}a\cap x\kappa\neq$$\mathrm{k}\mathrm{e}\mathrm{r}s=\kappa$

for every$s\in A^{+}$

Corolary 2.1. An automaton A $=(X,$ A,.
t for every s,tif ker st$\delta)$

is a$S\mathcal{L}(\mathcal{R}\mathcal{G})$-type if and only$\mathcal{L}Z(\mathcal{R}\mathcal{G})$-type if and only$\in A^{+}$$=\mathrm{k}\mathrm{e}\mathrm{r}s\vee \mathrm{k}\mathrm{e}\mathrm{r}$Corollary 2.2. An automaton A $=(X,A,\delta)$ is a.
t for every s,tif im st$\in A^{+}$$=\mathrm{i}\mathrm{m}$Prom Corolaries 1.2 and 2.2 we obtain :Corollary 2.3. An automaton
type.

$\mathcal{R}Z(\mathcal{L}\mathcal{G})$Remark. It can be easily show that$\mathcal{R}Z(\mathcal{G})=\mathcal{R}\mathcal{G}$-type if and only if it isand$\mathcal{L}Z(\mathcal{L}\mathcal{G})=\mathcal{L}Z(\mathcal{G})=\mathcal{L}\mathcal{G}$.

$\mathcal{L}Z(\mathcal{R}\mathcal{G})-$$\mathcal{R}Z(\mathcal{R}\mathcal{G})=$

Theorem 3. Let $A=(X, A,\delta)$ be an automaton. Then the following are
equivalent :(1) There exist a subset
of $X$ and an equivalence on $X$ such thatfor every $x\in X$ .
for every $a\in A$ and(2) There exist a subset
of $X$ and an equivalence on $X$ such thatandfor every $s\in A^{+}$ ,(3) $A$ is a group-type.
$\mathrm{Y}$$\mathrm{i}\mathrm{m}a=\mathrm{Y}and$$\kappa$$\mathrm{k}\mathrm{e}\mathrm{r}a=\kappa$$\mathrm{Y}\cap x\kappa\neq\emptyset$$\mathrm{Y}$$\kappa$$\mathrm{k}\mathrm{e}\mathrm{r}s=\kappa$$\mathrm{i}\mathrm{m}s=\mathrm{Y}$Asemigroup in$S\mathcal{L}(\mathcal{G})$is called a Cliford semigroup,

Corollary 3.1. An automaton A $=(X,A,\delta)$ is a Cliford semigroup type if.
t for every s,tt and ker stand only if im st$=\mathrm{i}\mathrm{m}s\cap \mathrm{i}\mathrm{m}$$\in A^{+}$$=\mathrm{k}\mathrm{e}\mathrm{r}s\vee \mathrm{k}\mathrm{e}\mathrm{r}$Theorem 4. Let $A=(X, A, \delta)$ be an automaton, and Let$a\in A\}$ ,. Suppose that$s\in A^{+},x\in X$ . Then the following are equivalent:
type.
(1) $A$ is.
(2)
for every $s,t$.
(3)
for every $s,t$$\kappa=\cap\{\mathrm{k}\mathrm{e}\mathrm{r}a :a\in A\}$$\mathrm{i}\mathrm{m}s\cap x\mathrm{k}\mathrm{e}\mathrm{r}$$\mathrm{Y}=\mathrm{U}\{\mathrm{i}\mathrm{m}a$$s\neq\emptyset$:

for every$a\mathcal{L}Z\cross \mathcal{G}\cross \mathcal{R}Z$$\mathrm{k}\mathrm{e}\mathrm{r}s_{\mathrm{Y}}=\mathrm{k}\mathrm{e}\mathrm{r}t_{\mathrm{Y}}$$\mathrm{i}\mathrm{m}s_{\kappa}=\mathrm{i}\mathrm{m}t_{\kappa}$$\in A^{+}$$\in A^{+}$

Corollary 4.1. With the assumption of Theorem 4, the following are equiv-

alent :
(1) $A$ is a

$S\mathcal{L}(\mathcal{L}Z\cross Ci\cross \mathcal{R}Z)$

type.

57
(2) ker syty
(3)for every s,tfor every s,t$=\mathrm{k}\mathrm{e}\mathrm{r}s_{\mathrm{Y}}\vee \mathrm{k}\mathrm{e}\mathrm{r}t_{\mathrm{Y}}$$\mathrm{i}\mathrm{m}s_{\kappa}t_{\kappa}=\mathrm{i}\mathrm{m}s_{\kappa}\cap \mathrm{i}\mathrm{m}t_{\kappa}$$\in A^{+}$$\in A^{+}$.

.

Suppose that an automaton $A$ is a
-type. As is seen in the
proof of Theorem 4, $A^{+}/\rho=\{(i,g,\mu) : i\in I, g\in G,\mu\in M\}$ . For $i\in I$ and$\mu\in M$ , let $A_{:}/\rho=\{(i,g,\mu) : g\in G,\mu\in M\}$ and $A_{\mu}=\{(i,g,\mu)$ : $i\in I$ , $g\in$, respectively. Thenand
. For $s\rho=(i,g.\nu),t\rho=$$(j, h, \mu)$ , since $(st)\rho=(i,gh, \mu)$ , by Theorems 1and 2, we have
. Thus we obtain ;and$\mathcal{L}Z\cross \mathcal{G}\cross R\prime Z$$G\}$$A_{:}/\rho\in \mathcal{R}\mathcal{G}$$A_{\mu}/\rho\in \mathcal{L}\mathcal{G}$$\mathrm{k}\mathrm{e}\mathrm{r}st=\mathrm{k}\mathrm{e}\mathrm{r}s$$\mathrm{i}\mathrm{m}st=\mathrm{i}\mathrm{m}t$

Corollary 4.2. If an automaton A is a
-type. The converse is not true,$\mathcal{L}Z\cross \mathrm{C}\mathcal{G}$$\cross \mathcal{R}Z$-type, then it is$a$$\mathcal{R}Z(\mathcal{L}\mathcal{G})$There is asimple example that a-type.
a$\mathcal{R}Z(\mathcal{L}\mathcal{G})$-type automaton which is not$\mathcal{L}Z\cross \mathcal{G}\cross \mathcal{R}Z$

References
1. Howie, J. M., “Fundamentals of Semigroup Theory”, Oxford Science Publications, Oxford, 1995.
2. Howie, J. M., “Automata and Languages”, Oxford Science Publications,
Oxford, 1991.

3. Petrich, M., “Lectures in Semigroups”, John Wiley and Sons, London, 1977.
4. Saito, T. Band-type acts over free monoids (preprint)