天邪鬼がオートマトンの導入をするとこうなる(自由生成された圏としてのオートマトン)

※このページはmathjaxの使い過ぎで表示が重くスマホでの閲覧に適しません。パソコンでも通信環境やスペックによっては数秒から数十秒放置してからスクロールを始めたほうがストレスがないかと思います。

どうも、Aaronです。

今回はとても天邪鬼にオートマトンの導入をしていこうと思います。

※この記事において「小さい」という言葉は「クラスに対して定義された概念が実際には集合で与えられている。」という意味でのみ用います。有限や可算であることを「小さい」と表現することはありません。

＊やや細かい集合論の知識を要求する箇所が一部ありますが、それ以外については若干の例外を除いてself-containedに書くつもりです。

1章準備(代数)

Def1.1 前代数系

前代数系 $\it {\rm (}X,\times,error{\rm )}$ とはクラス $\it X$ であって、必ずしも全域的でない二項演算 $\times$ を持つものである。概念上はそれだけなのだが、「全域的でない」という状況を現代数学の記法では書きにくいため、ここでは $\it error\not\in X$ をとり、 $\it \times{\rm :}X\times X\to X\cup \{error\}$ として定式化することにする。

前代数系 $X$ が「小さい」とか「有限である」というのは台クラス $\it X$ がそうであることである。

また紛れの恐れがないならば台クラスのみで前代数系を指定することがある。

Def1.2 局所半群

局所半群 $\it {\rm (}X,\circ,error{\rm )}$ とは前代数系であって、その演算が（必ずしも全域的でないが）等式の両辺が定義される限りにおいて結合的な、すなわち

$\it\forall\alpha,\beta,\gamma\in X.{\rm [}\alpha\circ\beta\neq error\land\beta\circ\gamma\neq error\rightarrow{\rm (}\alpha\circ\beta{\rm )}\circ\gamma=\alpha\circ{\rm (}\beta\circ\gamma{\rm )]}$

を満たすものである。ここで前件は後件の等式の両辺が定義されるために必要であるが、後件の等式が「両辺の値がともに $\it error$ 」を持って成立することも定義上は許容されることに注意せよ。

局所半群の演算 $\circ$ のことを以降では結合積と呼ぶ。

局所半群が「小さい」とか「有限である」というのは前代数系としてそうであることである。

また紛れの恐れがないならば台クラスのみで局所半群を指定することがある。

＊名称について・・・このような非常に弱い代数構造（全域的でないものは代数構造とすら呼ばないのかも知れない）の名前は「半(semi-)」とか「擬(quasi-)」とか「亜(-oid)」とかを適当に順につけたような呼び名ばかりであり、文献同士で衝突していることも珍しくない。最初この概念にはsemi-groupoidの訳として「半亜群」という言葉を当てていたのだが、groupoidという言葉自身に「結合的ですらなくてよいが全域的な二項演算を持つ体系」と「全域的でなくてよいが、単位元(ただしここでの単位律は「値を持つ限り」という意味で成立する)の存在(一意性を含まない)とその単位元に関する可逆性を満たし、しかも結合的な二項演算を持つ体系」という少なくとも二つの用法があることを思い出し、また後にもう一度触れるが「半」という接頭詞は「単位元・単位射を持たない」という意味で揃えて使いたかったため、今回一般的でない造語を用いることにした。Wikipediaによると全域的でない演算を「局所的」と呼ぶことがあるらしいため、このフレーズを用いて表現することにした。これはこれで「局所環」などと被ってしまうが、今回環や体は出てこないので許していただきたい。

Def1.3 局所モノイド

局所モノイド $\it {\rm (}X,\circ,error,ids{\rm )}$ とは、局所半群であって空でない集合 $\it ids\subseteq X$ が与えられており、

$\it\forall a.a\in ids\Leftrightarrow{\rm (}\forall b.{\rm [}a\circ b=b\lor a\circ b=error{\rm ]}\land\forall c.{\rm [}c\circ a=a\lor c\circ a=error{\rm ])}$

（単位律と呼ばれる）

を満たすものである。

局所モノイドが「小さい」とか「有限である」というのは局所半群としてそうであることである。

また紛れの恐れがないならば台クラスのみで局所モノイドを指定することがある。

Def 1.4 代数系

代数系 $\it {\rm (}X,\ \cdot\ {\rm )}$ とはクラス $\it X$ であって、全域的な二項演算 $\ \cdot\$ を備えたものである。

代数系 $X$ が「小さい」とか「有限である」というのは台クラス $\it X$ がそうであることである。

また紛れの恐れがないならば台クラスのみで代数系を指定することがある。代数系の演算 $\ \cdot\$ は単に積と呼ばれることが多い。

＊筆者の偏見かもしれないし、あるいは逆に筆者の不勉強でちゃんとした理由があるのかもしれないが、なぜか非全域的な演算には $\it\times$ や $\circ$ 、全域的な演算には $\ \cdot\$ が用いられる印象があるため今回の記事ではそうすることにする。全域的になると演算の記号が塗りつぶされる、という事になる。

Def1.6 半群

半群 $\it {\rm (}X,\ \cdot\ {\rm )}$ とは代数系であって、二項演算 $\ \cdot\$ が結合的なものである。全域的なのでここでの結合律は

$\it\forall\alpha ,\beta ,\gamma\in X.{\rm (}\alpha\cdot\beta{\rm )}\circ\gamma=\alpha\circ{\rm (}\beta\cdot\gamma{\rm )}$

という慣れ親しんだ形に戻る。

これは局所半群 $\it X$ であって

$\it\forall a,b\in X.a\circ b\neq error$

たるものであるといっても同じである。

半群 $X$ が「小さい」とか「有限である」というのは代数系としてそうであることである。

また紛れの恐れがないならば台クラスのみで半群を指定することがある。

Def1.7 モノイド

モノイド $\it {\rm (}M,\ \cdot\ ,id{\rm )}$ とは半群であって、単位元と呼ばれる元 $\it id\in X$ が与えられており、

$\it\forall a\in M. a\cdot id=id\cdot a=a$

を満たすものである。これは局所モノイドであって

$\it\forall a,b\in X.a\circ b\neq error$

たるものだといっても同じである。

ここで「局所モノイドでは複数の単位元の存在を許していたが同じなのか？」と思った読者は賢明である。もっと賢明な読者は同じである理由を知っていたかもしれない。今あるモノイド $\it M$ の $\it id$ と異なるかもしれない元 $\it id\ '$ も単位律を満たしたとしよう。このとき単位元の性質と仮定から

$\it id\ '=id\cdot id\ '=id$

となる。従って、モノイドの単位元たりえる元は唯一なのである。（ここで値を持たない( $\it error$ )という選択肢がなくなったことが有効に働いていることがわかるだろう。)

モノイド $X$ が「小さい」とか「有限である」というのは半群としてそうであることである。

また紛れの恐れがないならば台クラスのみでモノイドを指定することがある。

Def1.8 群

群 $\it {\rm (}G,\ \cdot\ ,id,{}^{\rm -1} {\rm )}$ はモノイドであって、さらに対応 $\it \ {}^{\rm -1}{\rm :}G\to G$ を持ち

$\it \forall a\in G.a^{\rm -1}\cdot a=a\cdot a^{\rm -1}=id$

(これは可逆律と呼ばれ、 $\it a^{\rm -1}$ を $\it a$ の逆元と呼ぶ。)

を満たすものである。

ちなみにモノイドの単位元の条件同様、群の逆元の条件をみたすものも(各 $\it a\in G$ ごとに)一意である。これは以下のようにしてわかる。ある $\it a$ に対して $\it a^{\rm -1}$ と同じとは限らないが可逆律と同じ等式を満たす $\it a^{\rm -1}_1$ があったと仮定すると、仮定と可逆律から下の等式が成り立つ。

$\it a^{\rm -1}_1=a^{\rm -1}_1\cdot id=a^{\rm -1}_1\cdot a\cdot a^{\rm -1}=id\cdot a^{\rm -1}=a^{\rm -1}$

群 $X$ が「小さい」とか「有限である」というのはモノイドとしてそうであることである。

また紛れの恐れがないならば台クラスのみで群を指定することがある。

＊群より強力な構造(可換群、環など)は今回出てこないので導入しない(群だって怪しいものだったのだが、ここまでやって導入しないのもおかしいかと思い導入した)。各自、一般的な代数学の教科書を参照のこと。

Def1.9 準同型

2つの前代数系 $\it X,Y$ の間の準同型 $\it f{\rm :}X\rightarrow Y$ とは以下を満たすような台クラスの間の対応である。

$\it\forall a,b\in X.{\rm [}a\times b\neq error\rightarrow f{\rm (}a\times b{\rm )}=f{\rm (}a{\rm )}\times f{\rm (}b{\rm )}{\rm ]}$

(これを「演算を保つ」と表現することが多い)

そのほか1章で定義した各構造についても同様に準同型が定義される。

ただし局所モノイド $\it {\rm (}X,\circ,error,ids_X{\rm )},{\rm (}Y,\circ,error,ids_Y{\rm )}$ およびモノイド $\it {\rm (}X,\ \cdot\ ,id_X{\rm )},{\rm (}Y,\ \cdot\ ,id_Y{\rm )}$ (あるいはさらにこれらの上位に位置する構造)に対する準同型 $\it f{\rm :}X\rightarrow Y$ は $\it ids,id$ についての追加の条件

$\it f(ids_X)\subseteq ids_Y\\f(id_X)=id_Y$

をも満たさねばならない。

ところで群の ${}^{\rm -1}$ に対しても準同型に追加の条件

$\it f{\rm (}a^{\rm -1}{\rm )}=f{\rm (}a{\rm )}^{\rm -1}$

を課すことが多いがこれは実は冗長である。すでに課されている条件から $\it a\cdot b=id_X$ ならば準同型 $\it f{\rm :}X\rightarrow Y$ に対して

$\it f{\rm (}a{\rm )}\cdot f{\rm (}b{\rm )}=id_Y$

が成り立つが逆元の一意性より $\it f{\rm (}a{\rm )}$ は $\it f{\rm (}b{\rm )}$ の、 $\it f{\rm (}b{\rm )}$ は $\it f{\rm (}a{\rm )}$ の逆元になるからである。

＊この節では異なる前代数系同士の演算の記号に同じものを用いてしまったが、とてもメジャーな記号の濫用なので誤解を生まないと信じたい。

2章準備(箙・圏・関手)

Def2.1 箙(えびら)

箙 $\it {\rm (}Q,A,Hom{\rm )}$ とは対象クラスと呼ばれるクラス $\it P$ と射クラスと呼ばれるクラス $\it A$ とホム対応と呼ばれる対応

$\it Hom{\rm :}Q\times Q\to {\mathcal P}{\rm (}A{\rm )}$

( $\rm{\mathcal P}(X)$ は冪集合(または冪クラス)を意味する。ただしクラスにおける冪とはその部分集合(部分クラスではなく)のなすクラスであることに注意せよ。これは(少なくともNBG集合論の下では)クラスを元に持つ集合やクラスは許されないからである。)

の組であり、かつ $\it Hom$ が $\it A$ の分割を与える(すなわち二条件

$\it \forall\alpha,\beta,\gamma,\delta\in Q.{\rm [}Hom(\alpha,\beta)\cap Hom(\gamma,\delta)\neq \varnothing\rightarrow {\rm (}\alpha=\gamma\land\beta=\delta{\rm )}{\rm ]}\\\displaystyle \bigcup_{\alpha,\beta\in Q}Hom{\rm (}\alpha,\beta{\rm )}=A$

を満たす)であるようなものである。

箙が「小さい」とか「有限である」というのは $\it Q$ と $\it A$ が共にそうであることである。

また紛れの恐れがないならば対象クラスのみで箙を指定することがある。

なお以降では対象クラスの元の事を対象、射クラスの元の事を射と呼ぶ。またホム対応の値域の元の事をホムと呼ぶことがある。

＊ここで導入された箙（またこの後導入される半圏や圏も）を「局所小な箙」と呼び、真のクラスであるような $\it Hom{\rm (}\alpha,\beta{\rm )}$ を許した定義をすることもある。しかしそのような定義は僕が知る範囲ではあまり恩恵が多くないし、そのくせ記述上の煩わしさか、少なくともNBG集合論では扱いきれない不厳密さかの少なくとも一方を代償に払うことになるためここでは局所小なものに限って箙（半圏、圏）と呼ぶことにする。

Def2.2 半圏

半圏 $\it {\rm (}S,A,Hom,\circ,error{\rm )}$ とは箙であり、かつその射クラスが結合積 $\circ$ を備えた局所半群であって、しかも $\it a,b\in A$ に対して

$\it a\circ b\neq error\Leftrightarrow \exists \alpha,\beta,\gamma\in S.{\rm [}a\in Hom{\rm (}\alpha,\beta{\rm )}\land b\in Hom{\rm (}\beta,\gamma{\rm )}{\rm ]}$

を満たしているとき（この論理式の後半の条件を「型が合う」などと表現することがある。）に言う。

半圏が「小さい」とか「有限である」というのは箙としてそうであることである。

また紛れの恐れがないならば対象クラスのみで半圏を指定することがある。

＊この「半圏」という用語が一般的である自信は全くないし、そもそも応用例もあまりなさそうなので特別な用語を割り当てない事のほうが多いのかもしれないが、ステップバイステップで条件を増やしていく導入のほうが統一感があってわかりやすかろうと思ったのと、群から単位元の存在性の仮定を外したものが半群なので、圏から単位射の存在性の仮定を外したものであるこれを半圏と呼んでも用語に違和感が少ないと感じたためこの名で導入した。

Def2.3 圏

圏 $\it {\rm (}C,A,Hom,\circ,error,ids,id{\rm )}$ とは半圏であり、射クラスが局所モノイドにもなっており、さらに全単射な対応 $\it id{\rm :}C\to ids$ が $\it id{\rm (}\alpha{\rm )}\in Hom{\rm (}\alpha,\alpha{\rm )}$ を満たすようなものである。ここでは $\it id$ について $\it id{\rm (}\alpha{\rm )}$ と一般的な写像の記法に従って記したが、多くの圏論の文脈では $\it id_\alpha$ と書かれる(そしてこの方がわざわざローマン体に戻して括弧を打つよりタイピングが楽である)ため、以降ではこちらを使うことにする。また圏では $\it ids$ の元を単位射、もしくは恒等射と呼ぶことが多い。

圏が「小さい」とか「有限である」というのは半圏としてそうであることである。

また紛れの恐れがないならば対象クラスのみで圏を指定することがある。

Fig2.4 ここまで定義されたもののまとめ

f:id:takumim97:20200623204321j:plain — まとめの図

Ex 2.5 一点圏

対象クラスがシングルトン(一点集合)であるような圏を考えると、どの二つの射も型が合うことから定義より合成積の全域性が回復し、射クラスが(小さい)モノイドになる。このような圏を一点圏という。このことから小さいモノイドを一点圏と同一視することがある。この記事ではこれ以上解説しないが、同様にモノイドより上位の構造は特殊な公理や追加の構造を備えた一点圏と思うことができる。

Def2.6 関手

2つの圏 $\it {\rm (}C,A,Hom,\circ,error,ids_C,id{\rm )},{\rm (}D,B,Hom,\circ,error,ids_D,id{\rm )}$ の間の関手 $\it F$ とは、圏の射クラスの間の準同型 $\it C\to D$ の事である。圏(実際には前圏)の条件から、 $\it C$ で型が合う射は $\it D$ でも型が合わなくてはならないため、対象同士の対応をも自然に誘導され、それが関数的になることに注意せよ。

Def2.7 反対圏と基本反変関手と反変関手

圏 $\it {\rm (}C,A,Hom,\circ,error,ids,id{\rm )}$ に対してその「反対圏と基本反変関手の組」とは圏 $\it C^{op}={\rm (}C,A^{op},Hom^{op},\circ,error,ids,id{\rm )}$ と全単射な対応 $\it opp{\rm :}A\to A^{op}$ の組であり、

$\it\forall \alpha,\beta\in C,a\in A.{\rm[}a\in Hom{\rm (}\alpha,\beta{\rm )}\rightarrow opp{\rm (}a{\rm )}\in Hom^{op}{\rm (}\beta,\alpha{\rm )}{\rm]}$

を満たすようなものである。

また2つの圏 $\it C,D$ の間のある対応が $\it C$ の基本反変関手 $\it opp$ と $\it C$ の反対圏 $\it C^{op}$ から $\it D$ への関手 $\it F$ との合成で得られるとき、そのような対応を一般に反変関手という。

Ex2.8 圏の直和、直積

2つの圏 $\it {\rm (}C_1,A_1,Hom_C,\circ,error,ids,id{\rm )},{\rm (}C_2,A_2,Hom_D,\circ,error,ids,id{\rm )}$ が与えられたとき、新しい圏を作る方法がいくつか存在する。

そのようなものの中で最も簡単なものの2つを紹介する。

2つの圏 $\it C,D$ の直和圏 $\it C_1\sqcup C_2={\rm (}C_1\sqcup C_2,A_1\sqcup A_2,Hom_{C_1}\sqcup Hom_{C_2},\circ,error,ids,id{\rm )}$ は単に対象クラスと射クラスをそれぞれ $\it C,D$ のそれの和クラスとし、ホム対応 $\it Hom_{C_1}\sqcup Hom_{C_2}{\rm (}\alpha,\beta{\rm )}$ を

$\it Hom_{C_1}\sqcup Hom_{C_2}{\rm (}\alpha,\beta{\rm )}=\begin{cases}Hom_{C_1}{\rm (}\alpha,\beta{\rm )}\ \ {\rm (if\ }\alpha,\beta\in C_1{\rm )}\\Hom_{C_2}{\rm (}\alpha,\beta{\rm )}\ \ {\rm (if\ }\alpha,\beta\in C_2{\rm )}\\\varnothing\ \ {\rm (otherwize)}\end{cases}$

で定め、結合積の演算は $\it C,D$ のものをそのまま使ったものであり、要するに2つの圏を単に並べただけであるようなものである。

また2つの圏 $\it C_1,C_2$ の直積圏 $\it C_1\times C_2={\rm (}C_1\times C_2,A_1\times A_2,Hom_{C_1} \times Hom_{C_2},\circ,error,ids,id{\rm )}$ は対象クラスと射クラスを $\it C,D$ のそれらの直積クラスとし、ホム対応 $\it Hom_{C_1}\times Hom_{C_2}{\rm (}{\rm (}\alpha,\beta{\rm )},{\rm (}\gamma,\delta{\rm )}{\rm )}$ は

$\it Hom_{C_1}\times Hom_{C_2}{\rm (}{\rm (}\alpha,\beta{\rm )},{\rm (}\gamma,\delta{\rm )}{\rm )}=Hom_{C_1}{\rm (}\alpha,\gamma{\rm )}\times Hom_{C_2}{\rm (}\beta,\delta{\rm )}$

で定め、結合積は順序対の成分ごとに結合積を取ったもので定めたものである。

この時 $\it C_1$ (resp. $\it C_2$ )から直和圏 $\it C_1\sqcup C_2$ へ、また直積圏 $\it C_1\times C_2$ から $\it C_1$ (resp. $\it C_2$ )へ以下のような非常に自然な関手が取れる。

< $\it C_1$ (resp. $\it C_2$ )から直和圏 $\it C_1\sqcup C_2$ への関手(包含関手)>

射クラスの包含写像(本記事では多くのコレクションにクラスを用いることを許してきたため、集合であるとの感覚を抱かせるかもしれない「写像」という言葉を避け、「対応」という言葉を好んで用いていたが「包含対応」という語彙は違和感が大きかったため、ここでのみ写像という言葉を使う。これは射クラスが集合であることを仮定しているわけではない。)によって誘導される関手が存在する。これを包含関手と呼ぶ。

<直積圏 $\it C_1\times C_2$ から $\it C_1$ (resp. $\it C_2$ )への関手(射影関手)>

$\it C_1\times C_2$ の各射(定義より順序対である)を、その第1成分(resp.第2成分)に出現する $\it C_1$ (resp. $\it C_2$ )の射に対応させる(第2成分(resp.第1成分)は無視する。)関手が存在する。これを射影関手と呼ぶ。

remark:これらの関手は非常に自然であるが、これらの関手が $\it C_1,C_2$ から直和圏 $\it C_1\sqcup C_2$ へ、また直積圏 $\it C_1\times C_2$ から $\it C_1,C_2$ への唯一の関手というわけではない。実際どんな2つの圏の間にも定関手(この記事では定義しない。きわめて簡単な概念なのでWikipediaなり他のだれかのブログなりで確認できるであろう)を取ることができ、 $\it C_1,C_2$ が単位射のみを持つ一点圏でない限り包含関手や射影関手は定関手ではない。

Ex2.9 箙によって自由に生成される圏

任意の箙 $\it {\rm (}Q,A,Hom{\rm )}$ は以下の方法によって、同じ対象クラス $\it Q$ を持ち、 $\it A$ を部分クラスに持つような射クラスを持つ圏 $\it\langle Q\rangle={\rm (}Q,\langle A\rangle,\langle Hom\rangle,\circ,error,ids,id{\rm )}$ に拡張することができる。これを「箙による圏の自由な生成」とよび、得られた圏 $\it\langle Q\rangle$ を、「箙 $\it Q$ によって自由生成された圏」と言う。

<構成>

(結合積は $\it a\ {\rm\hat{\circ}}\ b$ から誘導され、いずれの $\it Hom_n{\rm (}\alpha,\beta{\rm )}$ にも $\it a\ {\rm\hat{\circ}}\ b$ が含まれない $\it a,b\in\langle A\rangle$ に対して結合積は値無し( $\it error$ )と定義される。)

remark:上記の $\it Hom_n{\rm (}\alpha,\beta{\rm )}$ の構成の過程で導入された $\rm\hat{\circ}$ は形式的な積であり非自明な等号を持たない(それゆえ結合積の記号として導入した $\it \circ$ ではなくハットをつけて区別した記号を用いた)。ゆえに $\it \langle \widetilde{Hom} \rangle{\rm (}\alpha,\beta{\rm )}$ は演算に関する公理を満たさず、圏どころか半圏ですらない。 $\it \langle \widetilde{Hom} \rangle{\rm (}\alpha,\beta{\rm )}$ を結合律と単位律を満たす同値関係で割ることによって、はじめて演算の規則が成立した $\langle Hom\rangle{\rm (}\alpha,\beta{\rm )}$ を得るのである。また圏であるためには箙でなくてはならないため、最後の行の和集合が実際には非交和であることも確かめる必要がある。しかし構成法から明らかに等号が成り立つのは同じ $\it\langle Hom\rangle{\rm (}\alpha,\beta{\rm )}$ に属する元同士に限るため(厳密な証明を求めるなら、項の構成に関する帰納法により自明な等号が発生するのは同じホムの内部でだけであることを示し、その後同値関係で割る操作で異なる二つの $\langle\widetilde{Hom}\rangle{\rm (}\alpha,\beta{\rm )}$ に属する元が等しくはならない(なぜならば結合順で属するホムは変わらないためである。この事実もまた項の構成に関する帰納法で得られる)ことを利用すれば容易に得られる。)、この点は問題ない。

Explain2.10 箙からの圏の自由生成の直感的意味

定義から箙は多重辺を許し、しかも多重辺はそれぞれに区別があり、ループも許される有向グラフであると見做せる。

この見方において、その箙から自由生成された圏の射 $\it Hom{\rm (}\alpha,\beta{\rm )}$ は $\it \alpha$ から $\it \beta$ に至るパスの集合だという事ができる。

Ex2.11 文字列空間

対象クラスがシングルトンであるような箙 $\it {\rm (}{\bf 1},A,Hom{\rm )}$ によって、一点圏 ${\rm (}{\bf 1},\langle A\rangle,\langle Hom\rangle,\circ,error,ids,id{\rm )}$ を自由生成することを考える。このときの射クラス $\it\langle A\rangle$ として得られるモノイドを「文字集合 $\it A$ 上の文字列空間」などと呼ぶことがあり、特別に記号 $\it A^*$ で書かれることがある。文字列空間の元は文字列と呼ばれる。構成を見ればなんとなく理解できるように、文字列空間はモノイドとしてある意味で「最も一般の」ものである。

3章状態遷移系・オートマトン

Def3.1 添字づけられた箙

添字づけられた箙 $\it {\rm (}Q,A,Hom,I,ass{\rm )}$ とは箙と添字クラス $\it I$ と添え字対応対応 $\it ass{\rm :}A\to I$ の組である。

remark:一般に「添字づける」といった場合、対応の向きは逆であることもある。特にここでは一つの添字が複数の射に割り当てられて良い（が、逆に複数の添字を割り当てられた同一の射や、一つの添字も持たない射は許されない）ことに注意せよ。

また特に各 $\it\alpha\in Q$ に対して $\it ass$ の $\displaystyle\it\bigcup_{\beta\in Q}{\rm (}\alpha,\beta{\rm )}$ への制限が全単射になるとき、箙 $Q$ は「決定論的に添え字づけられている」ということにする（この用語もまた全く一般的なものではない。後の説明にこの条件に名前があると便利だったので割り当てたに過ぎない。)

Def3.2 モノイドで添字づけられた圏

モノイドで添字づけられた圏 $\it {\rm (}C,A,Hom,\circ,error,ids,id,M,\ \cdot\ ,ass{\rm )}$ とは圏であり、添字づけられた箙でもあり、かつその添字クラス $\it M$ が積 $\ \cdot\$ を持つモノイドであり、しかもその添字対応 $\it ass$ が局所モノイドの準同型であるときに言う。

Ex3.3 添字づけられた箙によって自由に生成されるモノイドで添字づけられた圏

Def2.9で行った箙からの圏の自由生成と同様にして、添字づけられた箙 $\it {\rm (}Q,A,Hom,I,ass{\rm )}$ からモノイドで添字づけられた圏 $\it {\rm (}Q,\langle A\rangle,\langle Hom\rangle,\circ,error,ids,id,\langle\ I\ \rangle,\ \cdot\ ,\langle ass\rangle{\rm )}$ を自由生成することができる。詳しく書けば

$\displaystyle \it Hom_0{\rm (}\alpha,\beta{\rm )}=\begin{cases} Hom{\rm (}\alpha,\beta{\rm )}\ \ {\rm(if}\ \alpha\neq\beta{\rm )}\\Hom{\rm (}\alpha,\beta{\rm )}\cup\{ id_\alpha\}\ \ {\rm (if}\ \alpha=\beta{\rm )}\end{cases}\\I_0=I\cup{\rm \{}id{\rm\}}\\\displaystyle Hom_{n+1}{\rm (}\alpha,\beta{\rm )}=Hom_n{\rm (}\alpha,\beta{\rm )}\cup\bigcup_{\gamma\in Q}\bigcup_{a\in Hom_n{\rm (}\alpha,\gamma{\rm )}}\bigcup_{b\in Hom_n{\rm (}\gamma,\beta{\rm )}}\{a\ {\rm\hat{\circ}}\ b\}\\\displaystyle I_{n+1}=I_n\cup\bigcup_{\mathcal{A},\mathcal{B}\in I_n}\{\mathcal{A}\ {\rm\hat{\cdot}}\ \mathcal{B}\}\\\displaystyle\langle \widetilde{Hom}\rangle{\rm (}\alpha,\beta{\rm )}=\bigcup_n Hom_n{\rm (}\alpha,\beta{\rm )}\\\displaystyle\langle\ \tilde{I}\ \rangle=\bigcup_n I_n\\\langle Hom\rangle{\rm (}\alpha,\beta{\rm )}=\langle \widetilde{Hom} \rangle{\rm (}\alpha,\beta{\rm )}/\sim_{\rm associativity\ and\ unit}\\\langle\ I\ \rangle=\langle\ \tilde{I}\ \rangle/\sim_{\rm associativity\ and\ unit}\\\langle ass\rangle{\rm(}id_\alpha{\rm)}=id\\\langle ass\rangle {\rm(}a{\rm)}=ass{\rm(}a{\rm)}\ \ {\rm (if}\ a\in A{\rm)}\\\langle ass\rangle{\rm (}a\ {\rm\hat{\circ}}\ b{\rm )} = \langle ass\rangle{\rm (}a{\rm )}{\rm\hat{\cdot}} \langle ass\rangle{\rm (}b{\rm )}$

(ここで導入された $\ \rm\hat{\cdot}\$ も、また $\ \rm\hat{\circ}\$ 同様形式的な演算であり同値関係で割ることで演算規則を回復していることに注意せよ。)

である。添字に関する部分が追加された分だけ見た目は煩わしくなったが、よく見ればほとんど変更がないことがわかるだろう。またこの構成で得られる添字モノイド $\it \langle\ I\ \rangle$ が実は文字列になることも、 $\it\langle\ I\ \rangle$ の構成が $\it I$ を箙の射クラスと思えば、 $\it\langle Hom\rangle$ の構成と全く同じであることからわかるだろう。

このような構成で得られるモノイドで添え字づけられた圏を「ラベル付き状態遷移系」と呼ぶことがある。

Def3.4 オートマトン

添字づけられた箙 $\it {\rm (}Q,A,Hom,I,ass{\rm )}$ によって自由生成された文字列空間で添字づけられた圏 $\it {\rm (}Q,\langle A\rangle,\langle Hom\rangle,\circ,error,ids,id,\langle\ I\ \rangle,\ \cdot\ ,\langle ass\rangle{\rm )}$ であって、初期状態とよばれる空でないクラス $\it init\subseteq Q$ 及び、受理状態と呼ばれる空でもよいクラス $\it acc\subseteq Q$ が与えられたものをオートマトンという。

オートマトンに対してその添字となる文字列空間の文字列 $\mathcal{A}$ であって、

$\it\exists\alpha\in init,\exists\beta\in acc,\exists a\in Hom{\rm(}\alpha,\beta{\rm)}.{\rm[}\langle ass\rangle{\rm(}a{\rm)}=\mathcal{A}{\rm]}$

を満たすものを受理文字列と言い、受理文字列全ての集合を受理言語という。

またオートマトンを生成する箙の添字が決定論的であり、しかも初期状態がシングルトンであるときオートマトンは決定型であると言い、そうでないとき非決定型であるという。

また少なくない文脈ではオートマトンという語は対象クラスが有限な場合に限って用いる。

Def3.5 オートマトンの直和・直積、反対オートマトン

オートマトン $\it C,D$ の直和は圏としての直和に、初期状態及び受理状態も単純に $\it C,D$ のそれの和クラスとして与えたものである。

しかしオートマトン $\it C,D$ の直積は圏としての直積ではない。状態クラスおよび初期状態及び受理状態も単純に $\it C,D$ のそれの積クラスであるが、射は積クラスの以下のような部分クラスになる。

$\it {\rm(}f,g{\rm)}\in Hom{\rm(}{\rm(}\alpha,\beta{\rm)},{\rm(}\gamma,\delta{\rm)}{\rm)}\iff ass_C{\rm(}f{\rm)}=ass_D{\rm(}g{\rm)}$

$\it where\ f\in Hom{\rm(}\alpha,\beta{\rm)}{\rm)},\ g\in Hom{\rm(}\gamma,\delta{\rm)}$

オートマトン $\it C$ の反対オートマトンは圏としての反対圏であり、初期状態及び受理状態は不変のものである。

Problem3.6 ★★

Def3.5で定義された三概念がそれぞれオートマトンであることを確かめよ。

Problem3.7 ★★★

Def3.5で定義された三概念は、特定の形式を持つ受理言語を持つオートマトンを作る方法論として有用である。どのような受理言語を作ることができるか、説明してみよ。

Problem3.8 ★★★★(not yet clearly solved by writer)

オートマトンの間に準同型を定義してみよ。直感的な定義は可能であるしそれはとりあえず整合的であるが初期状態と受理状態をどうするかは非自明である。回答は一通りとは限らない。

Problem3.9 ★★★★★(further research target of writer)

3.8で定義される同型は恐らくオートマトンの受理言語を理解するには細かすぎる。何らかの圏論的枠組みを用いてより緩い同型、ないしホモトピー的な概念を定義できないか？

Problem3.10 ★★★★★(further research target of writer)

豊穣圏のようなより高級な圏論的枠組みを用いてプッシュダウンオートマトンをはじめとするオートマトンの様々な変種を今回行ったような方法で記述せよ。

あとがき

いかがでしたでしょうか？とても天邪鬼な方法でオートマトンを導入してみました。一応定義は一貫させたつもりですが、この記事でオートマトンに入門するのは勧めません。むしろ一般的な定義と見比べてみるとよいでしょう。今回これをやったのにはいくつか意味があり、勿論一番は天邪鬼心を満たすことだったのですが数学的な理由もいくつかあります。

第一に、なんであれ「ある概念」をほかの概念や分野の言葉に言い換えることは、しておくとなにかいいことがある可能性があるという一般的な事実です。こうしておけばProblemであげたような圏論的枠組みが使える、少なくともその可能性があります。

第二に、一般的な定義に登場する「遷移関数」という概念がやや人工的に感じる(少なくとも僕にとっては)のに対し、この定義は一読してもらえばわかる通り「構造を生やしていったらいつの間にかできた」という感じのものであり、ある意味ではより自然であることです。

第三に、少し第一と被りますが圏論の言葉を用いて記述すると、オートマトン同士の積や和、準同型、ホモトピー同値などを考えるモチベーションや指針がわかりやすいと思われたことです。勿論一般的な定義ではこういうことを考えることができないわけではありませんが、やはりそれ自体が圏であることにすると少なくとも心情的には見通しがよいです。

さて内容についての話はこの程度にして少し今回の執筆前・執筆中の周辺談についてお話ししたいと思います。

今回の記事を書こうと思ったきっかけはいくつかあり、ひとつは自分が手慰みに作ったこんなトイコードhttps://repl.it/@takumim97/automata#main.scmでした(一応一般の非決定型オートマトンを定義できる。現在バグ取り中)。

別の一つは知り合いが組織した「論理学友の会」という団体の初の発表会があったことです。少し体調が不安定で発表できるかはわからないのですが、次回でもよいので一応発表資料に使えるようなブログを書いておこうと思ったわけです。

論理学友の会slack→https://w1591611733-7t9107570.slack.com/join/shared_invite/zt-exqosl9f-0UoPMiU4lcORnzGeu6qLbA#/

また今回の記事ではかなり基礎的な定義から行ったこともあり、僕が間違ったところもたくさんあったり、僕がふさわしい用語を知らない概念もありました。

それらについてアドバイスをいただいたtwitterの友人(@AlweLogic様、@amntksr様、@R_O_R_I_J_O様)に最大限の感謝をこめて。

※指摘・質問はtwitter:@sanjutsu_yu宛にしてもらえると気付くスピード・確率とも上がります(確実とは言ってない)。

1章 準備(代数)