形式言語理論のための代数

形式言語理論は、かなりの程度、代数的に定式化できます。例えば、形式言語の全体は順序半環、オートマトンはその順序半環を係数とする正方行列だと思えます。オートマトンの初期状態と終状態、オートマトンのあいだの模倣（simulation）関係なども行列により表現できます。

ここでは、できるだけ手短に形式言語理論のための代数、特に半環係数行列の概念を説明します。形式言語とオートマトンの基礎事項についても概要を述べますが、とてもラフな記述なので、他の資料や教科書で予備知識は仕入れておいたほうがいいでしょう。図を多用して幾何的・物理的な比喩を使うと分かりやすくなるとは思うのですが、今回は絵は描きませんでした。絵による説明はまたの機会に。

目標はオートマトンと模倣の圏を作ることです。オートマトンは代数的には正方行列となります。関係圏Rel（の部分圏）をインデキシング圏とするインデックス付き圏を作り、そのグロタンディーク平坦化としてオートマトンの圏を構成します。

内容：

形式言語の復習

Σをなんらかの集合だとしてアルファベットと呼びます。ここのシグマは総和記号ではないですよ。なぜか形式言語理論では、アルファベットをΣで表す習慣があるのです。Σの要素を記号（symbol）とか字（letter）と呼びます。

記号、つまりΣの要素を並べたものを語（word）、列（string）、文（sentence）などと呼びます（ここでは語とします）。語の全体をΣ^*と書きます。右上の星はクリーネスターで、次のような表示ができます。

• Σ^* = I + Σ + Σ² + Σ³ + ...

ここで、

1. I = {ε} で、εは空語（empty word）。
2. Σ² = Σ×Σ など、右肩は直積のベキ指数を表す。
3. プラス記号は集合の直和を表す。

x, y∈Σ^* に対して、

• x・y := (xとyをこの順で並べた語)

とします。x・y はxとyの連接（concatenation）です。

Σ^*の部分集合を言語と呼びます。つまり、「Xが言語 ⇔ X⊆Σ^*」。この定義から、アルファベットΣ上の言語の全体は、Σ^*のベキ集合Pow(Σ^*)となります。Lang(Σ) := Pow(Σ^*) と置きましょう。

零言語と単位言語は次のように定義されます。

• O := 空集合
• I := {ε} （εは空語）

X, Y∈Lang(Σ) に対して、足し算+と掛け算・を、

• X + Y := X∪Y
• X・Y := {z∈Σ^* | z = x・y となる x∈X, y∈Y がある}

と定義します。

次の事実を確認してみてください。

1. (Σ^*, ε, ・) はモノイドになる。
2. (Lang(Σ), O, +, I, ・) は半環（semiring）になる。

念のため「半環である」を詳しく言うと：

1. (Lang(Σ), O, +) は可換モノイドである。
2. (Lang(Σ), I, ・) はモノイドである。
3. 左右の分配法則が成立する。左分配法則だけ書くと、X・(Y + Z) = X・Y + X・Z

[追記]O・X = X・O = O も必要でした。[追記]

オートマトンの復習

Σ、Σ^*、Lang(Σ) などは前節のとおり。Sを集合として、δ:S×Σ→S を写像として、(S, Σ, δ) を決定性オートマトンと呼びます。Sはオートマトンの状態集合または状態空間、Σはアルファベット、δは遷移写像と呼びます。

通常のオートマトンの定義では、始状態（初期状態）と終状態が指定されますが、ここでは考えません。必要があれば、始状態と終状態は後から追加できるます。むしろ、後から別に考えたほうがスッキリします。

遷移写像δを拡張して、δ^*:S×Σ^*→S を定義しましょう。x₁, x₂, ..., x_n を記号（Σの要素）だとして、語xが x=x₁x₂...x_n と書けるとします。この仮定で、

• δ^*(s, x) := δ(...δ(δ(s, x₁), x₂), ..., x_n)

特に、δ^*(s, ε) := s と定義します。こうすると、

• δ^*(s, x・y) = δ^*(δ^*(s, x), y)

が成立します。つまり、S上にモノイドΣ^*が作用していることになります。

δ:S×Σ→S を、δ:S×Σ→Pow(S) という集合値写像に置き換えたものが非決定性オートマトンです。非決定性オートマトンの場合は、S×Σ×S の部分集合Tを使った定式化が便利です。

• (s, a, s')∈T ⇔ s'∈δ(s, a)

さらに、τ:S×S→Pow(Σ) を次のように定義します。

• τ(s, s') := {a∈Σ | (s, a, s')∈T}

δ, T, τは次のように関係します。

• s'∈δ(s, a) ⇔ (s, a, s')∈T ⇔ a∈τ(s, s')

決定性オートマトンにおいて、δからδ^*を作ったのと同様な手順で、δ^*, T^*, τ^*を作れます。

• δ^*:S×Σ^*→Pow(S)
• T^*⊆S×Σ^*×S
• τ^*:S×S→Pow(Σ^*)

τ^*について具体的な表示を述べておきましょう。x∈Σ^* を、x = x₁x₂...x_n （i=1, 2, ..., nに関して x_i∈Σ）の形で書くことにします。

• x∈τ^*(s, s') ⇔ s₀ = s、s_n = s' である s₀, s₁, ..., s_n∈S があって、x₁∈τ(s₀, s₁), x₂∈τ(s₁, s₂), ..., x_n∈τ(s_n-1, s_n) が成立する。

半環、ベキ等半環、順序半環

半環の定義は既に述べました。Hが半環だとは、Hに足し算と掛け算があることです。ただし、引き算は要求しません。引き算が自由に出来るなら環（ring）となります。

半環Hの足し算がベキ等のとき、つまり x + x = x （x∈H） が成立するとき、Hはベキ等半環（idempotent semiring; ISR）だといいます。

順序半環という概念には揺らぎがあるようですが、ここでは次の定義を採用します。

1. Hは半環である。
2. H上に順序≦が定義されている。
3. x≦y かつ x'≦y' ならば、x + x' ≦ y + y'
4. x≦y かつ x'≦y' ならば、x・x' ≦ y・y'
5. 0≦x

以上の条件を満たすHを順序半環（ordered semiring）と呼ぶことにします。0が最小元なので、Hに「負の元」は存在しません。

Hがベキ等半環のとき、H上に次のようにして順序を定義できます。

• x≦y ⇔ x + y = y

このようにして定義された≦が実際に順序であり、順序半環の公理も満たすことは練習問題とします。なお、順序半環がベキ等半環とは限らないのは、自然数の順序半環Nを考えれば明らかです。

HとJが半環のとき、f:H→J が半環の準同型写像であるとは、次が成立することです。

1. f(0) = 0
2. f(x + y) = f(x) + f(y)
3. f(1) = 1
4. f(x・y) = f(x)・f(y)

半環を対象として、半環の準同型写像を射とする圏を定義できます。この圏をSRngとしましょう。

同様に、ベキ等半環を対象として、半環の準同型写像を射とする圏も定義できます。この圏は、ISRとします。

順序半環のあいだの準同型写像は、半環の順同型写像に次の条件も加えます。

• x≦y ならば、f(x)≦f(y)

順序半環と順序半環の準同型写像の圏はOSRとします。

ベキ等半環Hを先の手順で順序半環とみなしたものをOrd(H)と書くことにすると、Ord(-)は関手に拡張できて、Ord:ISR→OSR となります。忘却関手 ISR→SRng、OSR→SRng をどちらもUと書くことにすると、Ord;U = U となります。これは、HとOrd(H)が同じ台（underlying object）の上に定義されていることを意味します。

基数条件と総和可能性

半環係数の行列の話をするために、基数に関する総和可能性に触れておきます。これは、厳密な議論をするには必要なことですが、あまり神経質になることもないと思います。

二種類の不等号 ＜, ≦ と集合の基数κの組を ＜κ, ≦κ の形で書きます。これにanyという記号を付け足した、{＜κ, ≦κ|κは集合の基数}∪{any} を基数条件と呼ぶことにします。

集合Sの基数をcard(S)と書くことにして、Sが基数条件を満たすとは次のことだとします。

1. Sが基数条件＜κを満たすとは、card(S)＜κ のこと。
2. Sが基数条件≦κを満たすとは、card(S)≦κ のこと。
3. Sが基数条件anyを満たすとは、Sは任意（特に制限なし）のこと。

基数条件を一般にχ（ギリシャ文字カイ）と表すことにして（つまり、χ∈{＜κ, ≦κ|κは集合の基数}∪{any}）、SET^χ := {Sは集合 | Sは基数条件χを満たす} と定義します。SET^χ は集合の集まり（クラス）になります。特に、SET^anyはすべての集合からなる集まりです。ωを可算基数とするなら、SET^＜ω は有限集合の全体、SET^≦ωは高々可算な集合の全体です。

Hが半環、Sは集合として、写像 x:S→H を、HのS-添字族（S-indexed family）と呼びます。χは基数条件として、Hがχ-総和可能（χ-summable）とは次のことです。

• Sが基数条件χを満たすなら、任意のS-添字族 x:S→H は総和 Σx を持つ。

いま出てきたシグマは総和記号です。Σがアルファベットか総和記号かは文脈で判断してください。総和に関しては、「可算な総和可能性」を参照して下さい。可算な総和可能性は、基数条件 ≦ω に関する総和可能性です。

半環係数の行列

では、行列の定義をします。通常の行列を少し一般化します。行列のインデックス範囲を整数区間だけではなくて任意の集合を許すとします。「はじめての圏論 その第2歩：行列の圏」を事前に読んでおくと理解が早いでしょう。

χを基数条件として、半環Hはχ-総和可能だとします。以下、S, T, UなどはSET^χに属する集合とします。AがS列T行の行列だとは、Aが S×T→H という写像であることです。(s, t)∈S×T に対するAの値（成分）は、A(s, t)と書きますが、A[t, s] := A(s, t) という記法も導入します。tとsの順序が逆になっていることに注意。

χ-総和可能な半環Hに対するS列T行の行列の全体を Mat^χ_H(S, T) と書きます。以下では、基数条件χは了解されているものとして省略して Mat_H(S, T) とも書きます。

行列の和や積は普通通りに定義すればいいのですが、ここでは、一気に行列の圏を定義してしまいましょう。H係数の行列の圏をMとすると、圏Mは次のように定義します。

• |M| = Ob(M) := SET^χ
• M(S, T) = Mor(M)(S, T) := Mat_H(S, T)
• id_S := λ(s, s')∈S×S.(s = s' なら1, それ以外は0)
• A∈M(S, T), B∈M(T, U) に対して、A;B = BA = C として、C[u, s] := Σ_t∈TB[u, t]A[t, s] 。

以上で、集合（ただし基数条件χを満たす）を対象として、H係数行列を射とする圏が出来上がります。恒等射は単位行列、射の結合（composition）は行列の積で与えられます。行列の和も考えると、各ホムセットが可換モノイドの構造を持つ圏になります。

圏の定義のためにMという記号を導入しましたが、以下ではMではなくMat_Hを圏の名前として使います。Mat_H(S, T)は圏Mat_Hのホムセットなので、記法の辻褄は合っています。

矢印記号の使い方がややこしいので、ここで注意しておくと：

• A:S→T in Mat_H ⇔ A:S×T→H in Set

つまり、圏Mat_Hにおける「SからTへの射」の実体は、集合圏Setにおける「S×TからHへの射」だということです。

行列 A:S→T in Mat_H の転置（transpose）A^t:T→S in Mat_H を、A^t(t, s) := A(s, t) として定義します。この定義は通常の行列の転置と同じです。転置は、圏Mat_Hの対象の上では恒等だとして、反変関手 (-)^t:Mat_H→Mat_H に拡張できます。

インデックス付き圏としての行列とブール行列

Mat_Hは圏ですが、ここで半環Hを色々と動かしてみます。Hはベキ等半環の範囲で動かすことにします。

χは基数条件として、ISR^χはχ-総和可能なベキ等半環の圏だとします。H∈|ISR^χ| をひとつ取ると、SET^χを対象類とした圏Mat^χ_H が出来るのでした。

Hに圏Mat^χ_Hを対応させる操作は、ISR^χ→CAT という関手に拡張できます。ここで、CATは、必ずしも小さいとは限らない圏の圏です。CATは恐ろしげな集まりですが、便利な略記法程度に考えてください。f:H→J in ISR^χ に対して関手 f_*:Mat^χ_H→Mat^χ_Jは次のように定義します。

• 対象S∈|Mat^χ_H| = SET^χ に対して、f_*(S) := S （恒等）。
• A:S→T in Mat^χ_H に対して、f_*(A) := A;f in Set と定義する。A' = f_*(A) とすれば、A'(s, t) := f(A(s, t)) と、成分ごとにfを適用することになる。

以上から、Mat^χ_f := f_* として関手 Mat^χ_-:ISR^χ→CAT が定義できました。これは、Mat^χ_- がインデックス付き圏（indexed category、正確には余インデックス付き圏）であることです。係数半環を色々と動かした行列圏の全体は半環の圏（今の例はベキ等半環の圏）の上にたくさんの行列圏が生い茂ったような構造なのです。

B := {0, 1} として、Bに通常のブール代数の演算を入れます。すると、Bはベキ等半環となります。よって、B∈|ISR^χ|。それだけではなくて、Bは、圏ISR^χの始対象となります。なぜなら、任意のベキ等半環は0と1を持つので、ブール代数の半環が埋め込まれているとみなせるからです。ベキ等半環Hに対して、i_H:B→H を唯一の埋め込みだとします（Hが潰れた単元の半環のときは例外的に埋め込みではありません）。

射 i_H:B→H に対して、関手 i_H^* = Mat^χ_iH: Mat^χ_B→Mat^χ_H が定義できます。この関手は、ブール行列（係数域がBである行列）を、任意係数の行列に埋め込む操作となっています。別な言い方をすると、どんな係数域の行列にもブール行列は自然に含まれるのです。

ところで、ブール行列の圏は実は関係圏と同じものです。関係圏Relのなかで、対象を基数条件χを満たす集合に制限した部分圏をRel^χとすると、Mat^χ_B はRel^χと同じものです。この意味で、Mat^χ_H はRel^χの拡張となっています。

正方行列とオートマトン

A:S→S in Mat^χ_H のとき、Aは正方行列です。H係数の正方行列Aはオートマトンとみなせます。唐突のようですが、オートマトンの定義を思い出してください。状態空間がS、アルファベットがΣである非決定性オートマトンは、τ^*:S×S→Pow(Σ^*) と表現できました。Pow(Σ^*) は Lang(Σ) のことで、Lang(Σ) は半環なのでした。H := Lang(Σ) と置いてみると、非決定性オートマトンは、S×S→H in Set と書けます。これはH係数の正方行列の定義に他なりません。

以上の理由から、半環係数の正方行列をオートマトンとも呼びます。ただし、係数半環Hとしてはベキ等半環または順序半環を採用します（ベキ等半環は自動的に順序半環です）。Aが、S→S in Mat^χ_H の形の正方行列のとき、Sをσ(A)と書くことにします。σ(A)は、正方行列としてはAの添字集合、オートマトンとしてはAの状態空間のことです。

添字集合がSであるH係数正方行列の全体を Autom_H[S] と書きましょう。もちろん、Autom_H[S] = Mat^χ_H(S, S) です。特に、H := Lang(Σ) とした、Autom_Lang(Σ)[S] は、状態空間SでアルファベットがΣであるオートマトンの全体です。

オートマトンのあいだの順序

ここから先では、半環Hは順序半環だとします。Hの順序は記号≦で書きます。Hがベキ等半環なら自然に順序半環とみなせるのでOKです。

さて、A:S→T、B:S→T を2つの行列（圏Mat_Hの射）だとします。行列に関する順序関係 A ≦ B を次のようにし定義します。

• A≦B ⇔ すべての (s, t)∈S×T に対して A(s, t) ≦ B(s, t)

要するに、すべての成分で不等号が成立しているとき、行列全体の不等号も成立します。単純な定義ですね。

いま定義した順序は、圏Mat_Hのホムセットごとに順序を入れたことになります。これにより、圏Mat_Hは順序豊饒圏（order enriched category）になります。A, A':S→T、B, B':T→U に対して次が成立します。

• A ≦ A'、B ≦ B' ならば、BA ≦ B'A'

特に、Mat_H(S, S) は順序半環になります。状態空間がSであるオートマトンの全体は、Autom_H[S] = Mat_H(S, S) と定義されるので、オートマトンのあいだにも順序が定義されます。

リダクトによる作用

行列をA, Bなどで表しますが、ブール行列はα、βなどのギリシャ文字で表すことにします。係数半環Hが何であってもブール行列はH係数行列とみなすことができます。行列成分が0か1である行列がブール行列です。ブール行列 α:S→T の実体は α:S×T→{0, 1} in Set なので、αはS×Tの部分集合を定義します。つまり、ブール行列はSからTへの関係とみなせて、関係圏Relの射ともみなせます。

α:S→T in Mat_H がブール行列、B:T→T in Mat_H は添字集合Tの正方行列だとします。α^tBα を、Bのαによるリダクト（reduct）と呼びましょう。用語「リダクト」は、適当な言葉が見つからなかったので、インスティチューション理論の言葉を拝借しました。

^αB := α^tBα と置くと、次の“指数法則”が成立します。δ = δ_T:T→T は単位行列だとします（遷移写像δと記号がかぶってますが、これも文脈で判断）。

1. ^α(^βC) = ^αβC （α:S→T、β:T→U、C:U→U）
2. ^δB = B
3. B ≦ B' ならば、^αB ≦ ^αB'

これらの法則は、定義からすぐに出ます。

インデックス付き圏 Autom_H[-]

基数条件χを固定して、Mat^χ_B を考えます。Bはブール代数の半環です。Mat^χ_B は、対象を基数条件χを満たす集合に限定した関係圏Rel^χと同じものです。Mat^χ_B = Rel^χ と同一視します。

Hはχ-総和可能な順序半環として、Hも以下固定します。Sを基数条件χを満たす集合として、状態空間SのH係数オートマトンの全体 Autom_H[S] は、Hの順序関係から導かれる行列の順序関係により順序集合です。ここで、順序集合は圏とみなせることを思い出してください。それは「はじめての圏論 その第3歩：極端な圏達」に書いてあります。

α:S→T をブール行列とします。αによるリダクトは、添字集合Tの正方行列を添字集合Sの正方行列に移します。つまり、^α(-):Autom_H[T]→Autom_H[S]。リダクトは順序を保つので、順序集合の準同型写像です。順序集合を圏とみなすなら、リダクト^α(-)は関手となります。

上記の状況をまとめると：

1. 集合Sごとに圏（とみなした順序集合）Autom_H[S] が対応している。
2. ブール行列 α:S→T に対して、関手 ^α(-):Autom_H[T]→Autom_H[S] が対応している。
3. 単位行列 δ:S→S には恒等関手 ^δ(-):Autom_H[S]→Autom_H[S] が対応している。
4. ブール行列 α:S→T、β:T→U に対して ^βα(-) は関手の合成 ^β(^α(-)) に等しい。

これは、Autom_H[-] がインデックス付き圏であることを意味します。このインデックス付き圏のインデキシング圏（定義域の圏、ベース圏）はブール行列の圏ですが、関係圏Rel^χと同一視できるので、オートマトンのインデックス付き圏は関係圏の上に広がっていると言えます。

オートマトンの圏 AUTOM_H

インデックス付き圏があったらグロタンディーク平坦化してみるのが定石です（「インデックス付き圏のグロタンディーク構成」を参照）。インデックス付き圏Autom_H[-]をグロタンディーク平坦化した圏をAUTOM_Hとしましょう。圏をAUTOM_H は次のように記述できます。

• AUTOM_Hの対象は、Autom_H[S]の対象をSを動かしながらすべて直和で寄せ集めたもの。|AUTOM_H| = Σ_S∈SET^χAutom_H[S] と書けます。
• A∈Autom_H[S] から B∈Autom_H[T] への射は、ブール行列 α:S→T と、A→^αB in Autom_H[S] という射で与えられる。Autom_H[S] の射とは順序関係なので、A ≦ ^αB が射である。

αによるリダクトを具体的に書くと A ≦ α^tBα、これがAからBへの射です。さらに、成分表示で書き下すと：

• A[s', s] ≦ Σ_{t', t}α[s', t']B[t', t]α[t, s]

この不等式を注意深く解釈すると、オートマトンのあいだの模倣になっていることが分かります。つまり、圏AUTOM_Hは、オートマトンを対象として模倣を射とする圏なのです。

その他の色々なこと

備忘のために、言い残した雑多なことを書きます。

通常のオートマトンの定義では、始状態（初期状態）と終状態がありますが、それは次のように定義できます。A:S→S in Mat_H がオートマトン（正方行列）だとして、ブール行列 ι:1→S （始状態）と φ:S→1 （終状態）を考えます。ここで、1は単元集合です。組 (A, ι, φ) を改めてオートマトンと定義して、オートマトンのあいだの射は次のように定義します。

A:S→S、B:T→T で、(A, ι_A, φ_A) と(B, ι_B, φ_B) は2つのオートマトンだとします。ブール行列 α:S→T が次の条件を満たすとき射とします。

1. A ≦ α^tBα （模倣条件）
2. ι_A ≦ α^tι_B
3. φ_A ≦ φ_Bα

このように定義すると、通常のオートマトン理論を再現できます。オートマトン (A, ι_A, φ_A) により定義される言語は、φ_AA^*ι_A:1→1 という1列1行の行列（事実上のスカラー）です。行列の不動点方程式（文法に相当する）の解が、適当なオートマトンによりφ_AA^*ι_Aの形で書けることが、正規言語の理論の中核的事実でしょう。

オートマトンは、言語の生成系であると同時に言語の認識系でもあります。与えられた語xが言語Xに所属するかどうかをオートマトンで判定できます。言語の生成と認識は、ある種の双対性（随伴性、共役性）があるようです。

この双対性を理解するには、ゾゾウスキ導分を使うのが良いのではないかと思っています。

• http://d.hatena.ne.jp/m-hiyama/searchdiary?word=%A5%BE%A5%BE%A5%A6%A5%B9%A5%AD
• http://d.hatena.ne.jp/m-hiyama-memo/searchdiary?word=%A5%BE%A5%BE%A5%A6%A5%B9%A5%AD

Lang(Σ)は、モノイドΣ^*の上のB値関数に畳み込み積を入れた半環で、ゾゾウスキ導分は、モノイドΣ^*の半線形表現を与えます。その表現空間（半線形空間）はLang(Σ)です。となると、行列の成分は言語というより、言語に作用する作用素と考えたほうがいいのかも知れません。作用素の代数は、ゾゾウスキ導分を含む（ゾゾウスキ半環とでも呼ぶべき）半環です。

これらのことを、マーク・ホプキンスの "The Quantum Field Theory - Computer Science" 対応の文脈で考えると面白いのではないか … とずっと思っているのですが、詳細は相変わらず不明ですね(苦笑)。