「オートマトンの圏」とかいうと、話がややこしくなるゾ

電波文騒ぎ（っていうほどの事ではない）のmixi掲示板見て思ったのだけど、「オートマトンの圏」ってば、誤解と混乱のもとではないか。

Rutten（ルッテンかなラッテンかな？）に倣えば、必ずしも有限ではない決定性オートマトンは、アルファベットA、状態空間S、遷移関数δ:A×S→S、終状態（判定関数）φ:S→{0, 1}からなる組(A, S; δ, φ)である（Ruttenは始状態を考えない）。

(B, T; δ, φ)がもうひとつのオートマトンだとして（δ、φは同じ記号を流用）、f=(f_al:A→B, f_st:S→T)がオートマトンの射だとは：

1. δ(f_al(a), f_st(s)) = f_st(δ(a, s))
2. φ(f_st(s)) = φ(s)

これで、圏Automができる。必要があれば、射の定義を拡張してもよい（例：f_alをletterに列を対応させる関数にする）。Aを固定して、f_alをAのidentityにすれば、Aごとに圏Autom_Aができる。これを使って、アルファベットの圏の上のindexed categoryにすることもできる。

全然別な例

普通、「オートマトンの圏」といえば、上のような定義だろう（いろいろと変種、拡張はありえるけども）。だが、1つのオートマトン(A, S; δ, φ)から圏を作ることもできる（φは関係なくなるが）。

まず、δ(a, s) = tのとき、sからtにarrow a があるとみなす。この方法で、Sを頂点集合として、Aでラベル付けされた有向グラフができる。このグラフから自由生成された圏をCとする。

Obj(C) = S、C(s, t) = {頂点sからtに至るすべてのパス}。パスの道筋を無視して、パスに出現するラベル列を取り出す写像をLabelとすると、Labelは圏Cからモノイド(A^*; ・, ε)（・は列の接合、εは空列）への関手となる。ただし、モノイドは単一対象上の圏とみなす。特に、homset C(s, t)のLabelでの像は、始状態s、終状態tにより生成される言語になる。

これも、特定のオートマトンから作り出した圏だから「オートマトンの圏」と呼べる。個々のオートマトンをこの方法で圏とみなせば、最初に出したオートマトンの圏は、「圏の圏」の例となる。