数理解析研究所講究録 1222 巻 2001 年 123-127

123
An Automaton for Deciding Whether
a Given Set of Words is aCode.
天理大学教養部

辻佳代子 (Kayoko Tsuji)

Faculty of Liberal Arts,Tenri University
words on an alphabet

For given finite set $X$$A$, it is well-know that there is analgorithm for deciding whether the set $X$ is acode (see [1]). In this paper, we define theambiguous word which has more than two factorizations
automatonin$fl_{X}$$fl_{X}$

such that the set $L(fl_{X})$ recognized by$\mathrm{i}\mathrm{n}X^{*}$$fl_{X}$is the set of all ambiguous words.We show that agiven set $X$ of words on an alphabet

set $L(H_{X})$ recognized by$fl_{X}$aproper prefix of some word in $X$ }.Let$p\in P(X)$$\varphi$

is code if and only if that theis empty.

For finite set $X$ of words on an alphabet

injection

and we construct an$c_{1}$we denote by $P(X)$ the set { $p\in X|p$ isbe the cardinality of $P(X)$ .Then, there is anfrom $P(X)$ into the set of natural numbers such that. We also denote by $S(X)$ the set {There is an injection$s\in A^{*}|s$$1\leq$ $\varphi(p)\leq \mathrm{q}$for everyis proper suffix of some word in $X$ }.

from $S(X)$ into the set of natural numbers such that $c_{1}+1\leq$$?\rho$$\psi(s)$forevery $s\in S(X)$ .
Now, we construct an automaton $flx$ overA inductively. The edges and states ofare defined by the following rules. Let$(\mathrm{P}(\mathrm{X}))$is state of$fl_{X}$$i$$fl_{X}$be the unique initial state of $ftx$ .Every element of

and, for every word $p$ in $P(X)$ ,$i-=_{\varphi(P)}$is apath in$\iota\ell=p^{-1}x.\mathrm{s}$$\iota\pi_{X}$.As every word

suffix of

$x$

$p$

, that is,in $P(X)$ is proper prefix of some word$u$is in $S(X)$ .Then,$\psi(u)$is state of$fl_{X}$$x$

in $X$ , ffie word

and$\varphi(p)rightarrow^{l}\psi(u)$is apath in$\backslash \pi_{X}$.If$\mathrm{t}\mathrm{p}(\mathrm{u})$is astate of $flx$ and if, for sojne word$v$

in $S(X)$ , the concatenatio

124
is written of the form

$uv$($uv$ $-x_{1}\cdots x_{nl}$then, $?P(v)$ is astatc of$ff_{X}$$x_{1},\cdots.,x_{m}$is in$fl_{X}$and$v$

is proper suffix of)$x_{m}$

and$\psi(u)arrow\psi(\nu v)$

is path in $flx$ Since $\varphi(P(X))\cup\psi(S(X))$ and $S(X)$ are finite, this procedure has finitesteps. Let

be the set of all states of$Q$$\psi(S(X)\cap X^{*})\cap Q$

word

$w$

$fl_{X}$.The set of terminal states of$fl_{X}$is the set.
if there exist words

is said to be mbiguous$x_{1}$,$\cdots$,$x_{m},y_{1}$,$\cdots$,$y_{n}$

of $X$

such thatand$w-x_{1}\cdots x_{m}-y_{1}\cdots y_{\hslash}$$x_{1}\cdots$$x_{i}\neq \mathrm{A}$$\ldots$

Theorem. For agiven set $X$ on an alphabet
automaton$fl_{X}$$(i-1\cdots,m -1, j- 1,\cdots, n-1)$$y_{j}$$A$.

, the set $L(tfx)$ recognized by theftx is the set of all ambiguous words in

Proof. Let $w\in L(fl_{X})$ .There exist $x_{1}\in P(X)$,.

$X^{*}$$x_{2}$,$\cdots$,$x,$,$\in S(X)$ $x,$ $\in S(X)\cap X^{*}$

suchthat $w-x_{1}x_{2}\cdots x$, and succesible path.
$...arrow q_{-1},q\underline{x}$$i^{\underline{-}}\underline{l}arrow- q_{1}-Barrow q_{2}arrow$where$q_{1}-\varphi(x_{1})$$\varphi(P(X))$,$q_{1}\mathrm{i}\mathrm{s}$, $q_{2}-\psi(x_{2})$ ,$\cdots$, $q,$ $-\psi(x,)$ and$q_{r}$

is aterminal state. Since$q_{1}\approx$$\varphi(x_{1})$is in

not terminal state. If $r-2$ , then$i\sim \mathfrak{g}^{\Leftrightarrow}q_{2}\underline{\underline{X_{1}}}$is succesible. By the definition of$fl_{X}$

Iaet $r>2$ .By the definition of,$w-x_{1}\Leftrightarrow\cdots x$$fl_{X}$

the word $w-x_{1}x_{2}$ itself is in $X$. Thus,$x_{1},x_{k- 1}x_{k},x_{r}$$(k-2,\cdots, r)$

are words of$w$$X^{*}$is ambiguous.
, thus, has two factorizations:.

$w-yp_{2}\cdots y_{ll}-z_{1}z_{2}\cdots z_{\hslash}(y_{1}, \cdots,y_{m},z_{1}, \cdots,z_{n}\in X)$

We show that$y_{1}y_{2}\cdots$of$y_{i}-\mathrm{z}\mathrm{f}\mathrm{a}\cdots$$x_{\mathrm{r}h}\cdots x_{t}$$fl_{X}$$yy_{2}\cdots$ $y_{j}\neq$ $z_{1}\Leftrightarrow\cdots z_{J}$for some , .TOae exists$i$$z_{j}$and thatfor all $i-1\cdots$ ,$y_{1}y_{2}\cdots$, wc may assume thatmust be asubwords of$y_{i}$$x_{t}x_{t*1}$$j$$y_{i}-z_{\mathrm{l}}\mathrm{g}\cdots z_{j}$$x_{t}$$m$, $j-1\cdots$ , .Suppose thatsuch thatis not aprefix ofis subwords of. It is impossible$n$$x_{t-1}x_{t}$, then$yp_{2}\cdots$ $y_{i}-z_{\mathrm{l}}\mathrm{g}\cdots z_{j}$$x_{1}x_{2}\cdots x_{t- 1}$$x_{t}$

is aprefix. By the definition ofis suffix of$y_{\mathrm{i}}$.However,$z_{j}$

125
Let

$w$

be ambiguous and$y_{1}y_{2}\cdots y_{i}\neq z_{1}\Leftrightarrow\cdots z_{j}$prefix of$y_{1}$. Since$w$

for all$(y_{1}, \cdots, y_{m}, z_{1}, \cdots, z_{n}\in X)$$warrow y_{1}y_{2}\cdots$ $y_{m}arrow z_{1}z_{2}\cdots$ $z_{n}$$i\approx 1\cdot\cdot..,m$, $j-1$$\cdots$, .We may assume that$n$is ambiguous, there exist , ,$\dot{*}$$i_{2}$$\cdots$, ,$j_{1}$$j_{2}$,$z_{1}$,

is proper

such that the following$\cdots$

conditions are satisfied:$y_{1}$

is proper prefix of$z_{1}z_{2}\cdots$Let$y_{m}$$x_{1}=z_{1}^{-1}y_{1}$and if$x_{r}=$$x_{2}=y_{1}^{-1}z_{1}z_{2}\cdots$$z_{j_{1}}$$z_{k}z_{k+1}\cdots$$z_{n1}$$z_{n}$

and,is asuffix of$(z_{1}\mathrm{z}_{2}\cdots z_{k-1})^{-1}y_{1}y_{2}\cdots$

suffix of$z_{j_{1}}$is proper prefix of$z_{j_{1}}$,$z_{1}z_{2}\cdots$$y_{m}\approx$$y_{k- 1}y_{k}\cdots$ $y_{m}$$y_{1}\cdots$$x_{3}\approx$$z_{n}$$y_{i_{t}}$$z_{1}\mathrm{z}_{2}\cdots$

and not aprefix of$(z_{\mathrm{I}}\mathrm{z}_{2}\cdots z_{j_{1}})^{-1}y_{1}y_{2}\cdots$$y_{\mathrm{i}}$and$y_{m}$$z_{k}\cdots$

and not aprefix of. If$z_{k- 1}z_{k}\cdots$ $z_{m}$$y_{m}$

is not, then we set,$z_{j_{1}- 1}$$y_{1}\cdots y_{i_{l}- 1}$$\cdots$.If$z_{n}$

is proper prefix ofis not, then we set

is aproper prefix of$z_{n}$and if$y_{k}y_{k+1}\cdots$ $y_{m}$$(y_{1}y_{2}\cdots y_{k- 1})^{-1}z_{1}z_{2}\cdots z_{\hslash}\approx y_{k}\cdots y_{m}$$x_{r}=$

is a.

Then, we have asuccesible path$i-^{\underline{X}\underline{X}\underline{X}}qq_{2}arrow\cdotsarrow q_{r-1}q_{r}$where$q_{1}=\varphi(x_{1})$, $q_{2}=\psi(x_{2})$, $\cdots,q_{r}=\psi(x_{r})$ . q.e.d.

The proposition yields the following corollary immediately.

Corollary.

given set $X$ on an alphabet

recognized by the automaton$fl_{\chi}\mathrm{o}\mathrm{f}X$$fl_{\chi}$and we show thatis acode if and only if the set $L(fl_{X})$is empty.

Example 1. Let $A=\{a.b\}$ and letconstruct$A$$\mathrm{L}(\mathrm{t}\mathrm{f}\mathrm{x})$, aabb, aabbab, $aba$ , $baa$ ,bbaaba}. We$X=\mathrm{f}\mathrm{y}\mathrm{a}\mathrm{b}$is empty, therefore, $X$ is acode.

It is clear that $P(X)\approx$ {$aab$, aabb}. We define abijection$\varphi(aab)=1,\varphi(aabb)\approx 2$aabbab , then$b$by. Since $aab$ is prefix of aabb, aabbab and aabb is prefix of, $bab$ , ab are inof natural numbers such that$\mathrm{P}(\mathrm{X})$.We can define an injection$\psi$, $\psi(bab)\approx 4,\psi$ (ab)\approx 5. Since$\psi(b)\approx$ $3$

bbaaba and ab is aprefix of $aba$ , then $aa$ , baaba ,of any word$\varphi \mathrm{P}(\mathrm{X})arrow\{\mathrm{L}2\}$$a$from $S(X)$ into the set$b$

is aprefix of $baa$ ,are in $S(X)$ . But, $bab$ is not prefix, therefore the state $\psi(bab)=4$ is not coaccessible. Continuing this process,$\mathrm{o}\mathrm{f}X$

we have the following automaton:

126

where 9$(\mathrm{a})-6$,$\psi$(baaba)-7,$\psi$(bbab) $)-8,\psi(a)-9$, $\psi(ba)-10,\psi(abb)-11$,$\psi(bb)-12$ , $rp(aaba)$ $-13$, $rp(abbab)-14$of$fl_{X}$. Since $S(X)\cap X$ -{afca} and, there is no terminal state in Slx, thus $L(fl_{X})$ is empty and $X$ is$\mathrm{t}\mathrm{p}(\mathrm{b}\mathrm{a}\mathrm{b})$is not astate

code.

Example 2. Let $A-\{a.b\}$ and let $X-tyaaaba$ , $aba$ , abab, bab9 babaaa, $bba$ }. We

construct$fl_{X}$. In this case$\mathrm{L}(\mathrm{t}\mathrm{f}\mathrm{x})$is not empty, therefore, $X$ is not acode.

It is clear that $P(X)-\{aba, bab\}$ .We deffie a bijection $\varphi:P(X)arrow\{12\}$ by$\varphi(aba)-tp(bab)$ $-2$

The set of all states$Q$.We have the following automaton:

is $\{\psi(aba )=1$ , $\mu_{bab})=2$, $\mu b)=3$ , $rp(abaaa )=4$ , $uab)=5$ , $\psi(ba)=6$,, $\psi(aba )=8$, $\psi(a)=9$, $\psi(baaa )=10$ , $\psi(aaba )=11$ , $\psi(bab)=12\}$ .The set of all$\mu aaa)=\mathit{7}$127
terminal states is$\mathrm{S}(\mathrm{X})$$Q-${ uaba $)=8$ , $\mu bab)=12$ }. Since $tp(aba )=8$ is terminal

state, apath$6arrow 3\underline{aba}bub$$i1arrow
3arrow$.

ab5

ab$5 arrow\frac{bab}{\overline{J-}}a12arrow 78aaa\underline{au}$is successible, thus w-ababbabababababaaaaba is accepted byIn fact,$w$$fl_{X}$

and$w$is ambiguous.

has two factorizations$w=(aba\cross bba\cross bab\mathrm{X}aba\cross babaaa\cross aba)-$($abab\cross bab\cross abab\cross abab\cross$ aaaaba)

in $X$.

Reference[1] J. Berstel&D. Peirin, Theory of codes, Academic Press, 1985