このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

形式言語理論とメイヤー流クラスと圏論

昨日の記事「マイヒル/ネロードの定理の入り口」の最後の一節:

普遍的なオートマトン構成法としてのマイヒル/ネロードの定理という話題は、何年も前から書こうとしていて先延ばしになっている話題なんですよね。「メイヤーオートマトンに関するマイヒル/ネロードの定理を宣伝する」でその「ありがたみ」はけっこう書いたのですが、内実が書いてないです。今回は、本来の(だが一側面に過ぎない)形である形式言語理論におけるマイヒル/ネロードの定理について書きました。いつか、内実と全貌を記述したいとは思っています。

一般化されたマイヒル/ネロードの定理は、広い範囲に渡る主張なんで、「内実と全貌の記述」は長い話になります。一度に長い話も無理なんで、チビチビと書いていくことしか出来ませんね。で、今日もチビチビのひとかけらを述べます。

形式言語理論のオートマトンとメイヤー流のクラス

形式言語理論では、言語を認識(受理)するオートマトンを考えます。メイヤー先生が推奨するオブジェクト指向設計・プログラミングでは、CommandメソッドとQueryメソッドが分離したクラスを考えます。この2つの概念は次のように対応してます。

形式言語理論 メイヤー流クラス
オートマトンの始状態 クラスのConstructor
オートマトンの終状態 クラスのQuery
言語のアルファベット クラスのCommand

オートマトンの状態空間をSとして、始状態の集合をI、終状態の集合をFとします(I⊆S、F⊆S)。話を簡単にするために、始状態が1個だけあり、それをiとします。I = {i} ですね。

始状態iと終状態の集合Fを、どちらも写像として表現します。次の方法を使います。

  • 1 = {0} を単元集合として、ι(0) = i と定義される写像 ι:1→S を考える。(「ι」はギリシャ文字イオタ)
  • B = {true, false} を真偽値の集合(二値ブール代数)として、「s∈F ⇔ φ(s) = true」である写像 φ:S→B を考える。

ι:1→S は、状態空間Sの要素iをポインティングする写像、φ:S→B は、状態空間Sの部分集合Fの特性関数(characteristic function)となる写像です。

言語のアルファベットをAとして、Aの要素(個々の記号)も写像として解釈します。オートマトンの遷移写像をδとすると、δ:S×A→S です。状態点sが入力記号aによりs'に遷移することは、δ(s, a) = s' と書けます。アルファベットAに属する記号aに対して、次の写像が定義できます。

  • a^ = λs∈S.δ(s, a)

a∈A を固定すると、a^:S→S; s|→δ(s, a) という写像が得られます。

以上をまとめると:

  1. 始状態iは、ι:1→S により表現できる。
  2. 終状態の集合Fは、φ:S→B により表現できる。
  3. アルファベットの記号aは、a^:S→S により表現できる。

クラスとは、状態空間とそこに働くメソッドの集まりですから、上記の事実は次のように述べることができます。

  1. 始状態iは、ι:1→S というConstructorにより表現できる。
  2. 終状態の集合Fは、φ:S→B というQueryより表現できる。
  3. アルファベットの記号aは、a^:S→S というCommandにより表現できる。

つまり、言語を認識するオートマトンは、メイヤー流のクラスとして解釈可能だということです。

圏論的解釈を少し

ι:1→S、φ:S→B、a^:S→S はいずれも写像です。集合圏(場合により部分写像の圏や関係の圏)のなかで、ι、φ、a^達を含む部分圏を考えましょう。最小の圏としては; 1、S、B の3つの対象、それぞれの恒等射と ι、φ、それから a∈A に対するa^達を基本的な射とする圏が定義できます。

この最小の圏をCとすると、そのホムセットの生成元の集合は次のようになります。([追記]←誤解を招くかもしれない表現なので、注*1も見てください。[/追記]

  • C(1, S) の生成元集合: {ι}
  • C(S, B) の生成元集合: {φ}
  • C(S, S) の生成元集合: {a^ | a∈A}

Cを作るには、上記のι、φ、a^達の組み合わせ(composition)を可能な限り作ればいいのです。

Cは比較的に小さな圏(割と可愛い圏)ですが、適当な指標に対する代数構造と余代数構造の両方を持つモデルともみなせます。

圏論的解釈を含めての対応表は次のようになります。

形式言語理論 メイヤー流クラス 圏論
オートマトンの始状態 クラスのConstructor C(1, S) の生成元
オートマトンの終状態 クラスのQuery C(S, B) の生成元
言語のアルファベット クラスのCommand C(S, S) の生成元

*1:{ι} が C(1, S) の生成元集合だと言っても、 ιだけでホムセット C(1, S) を生成できるわけではないです。{ι}∪{φ}∪{a^ | a∈A} により圏全体を生成しますが、それらの生成元のなかでιは ι:1→S という形をしている、という程度の意味です。