S型オートマトンとT型オートマトン

オートマトンの連接問題は「S型オートマトンとT型オートマトン」を考えるとケリが付く。Sはsubexpression、Tはtotal expressionから。

S型オートマトン

アルファベットA上のS型オートマトンとは、無音記号（εと同じ）を#として、A∪{#}で辺ラベル付けされた有向グラフで、スタートノード'-'とゴールノード'+'が特定されているもの。次の条件を満たす。

1. out('+')= 0 ゴールでオシマイ、もう後はない。
2. In('+') = {#} ゴールには無音記号でのみ到達できる。

アルファベットA上のS型オートマトンの全体は S-Aotom_A とする。Aがわかっているなら省略する。S-Automは連接演算でモノイドとみなす。MとNの連接は、M;N または MNと記す。

• MのゴールノードとNのスタートノードを同一視することが連接
• モノイド単位オートマトンは、('-' - # --> '+')

実際には、これではモノイドにならないけど、それでいいのだ。オートマトンを1セルとみなして、自然同値を与える2セルにより、擬モノイドとなる。2セルは双模倣だろうが、#辺を消去する手続きとその逆を考えるだけでもいいと思う。先に2セルの亜群構造があり、その亜群による弱等号に関してのモノイド概念。E集合＝セットオイドの圏内でのモノイドでもあるな。

T型オートマトン

アルファベットA上のT型オートマトンとは、無音記号（εと同じ）を#、終端記号を$として、A∪{#, $}で辺ラベル付けされた有向グラフで、スタートノード'-'とゴールノード'+'が特定されているもの。次の条件を満たす。

1. out('+')= 0 ゴールでオシマイ、もう後はない。
2. InL('+') = {$} ゴールには無音記号でのみ到達できる。
3. $∈InL(p) ならば p = '+'

アルファベットA上のT型オートマトンの全体は T-Aotom_A とする。Aがわかっているなら省略する。T-Automには自然な連接演算は定義できない。

MがS型オートマトンで、XがT型オートマトンのとき、モノイド作用（スカラー積）を定義できる。

• M*X は、MのゴールノードとXのスタートノードを同一視したもの

等号を弱い等号と解釈して、次が成立する。

• (MN)*X = M*(N*X)
• I*X = X

相互変換

MがS型オートマトンのとき、Mのゴールノードに至る辺の#を$に書き換えるとT型オートマトン。この変換を M^$ で表す。

• (-)^$ : S-Automo→T-Autom

$を#に書き換える変換を (-)^#: T-Automo→S-Autom とすると、互いに逆変換で：

1. (M^$)^# = M
2. (X^#)^$ = X

S-Automがベクトル空間、T-Automがベクトル空間と同型なアフィン空間に類似している。

次は重要。

• (M*X)^# = M(X^#)

T-Automの連接

2項演算 (-・-):T-Autom×T-Autom→T-Autom を次のように定義する。

• X・Y := X^#*Y

すると次が成立する。

1. (X・Y)^# = X^#Y^#
2. I^# = I （厳密には、左右のIは違うもの）
3. (MN)^$ = M^$・N^$
4. I^$ = I （厳密には、左右のIは違うもの）

つまり、S-Autom×S-Autom, S-Autom×T-Autom, T-Autom×T-Autom にそれぞれ積があり、うまいこと同調している。

なお、T-Automには左自明モノイド演算を定義することもできるが、これはEOFによりファイルが切れてしまう現象に対応する。あるいは、'\0'まで込めたconcat-copyの例も同じ。

[追記]シーケンスデータのインスタンスは特殊なオートマトンであることを忘れないように。[/追記]