Preliminares

有限機械

有限オートマトン、Moore machine とも.

有限機械 MM とは次の要素からなる:

  1. 有限集合 S=S(M)S = S(M): 状態 (statuses) と呼ぶ
  2. 有限集合 I=I(M)I = I(M): 入力 (inputs) と呼ぶ
  3. 有限集合 O=O(M)O = O(M): 出力 (outputs) と呼ぶ
  4. 関数 t:S×ISt: S \times I \rightarrow S: 遷移関数 (transition function) と呼ぶ
  5. 関数 o:SSo: S \rightarrow S: 出力関数 (output function) と呼ぶ
  6. ある一つの状態 ι\iota: 初期状態 (initial state) と呼ぶ

この本では状態にはギリシア文字 (α,β,\alpha, \beta, \ldots) を用い、 入力には a,b,c,a,b,c,\ldots、 出力には i,j,ki, j, k を用いる. また、t(α,a)t(\alpha, a)αa\alpha_a と略記する.

有限機械はある時点である状態 α\alpha を持ち、 連続的に出力 o(α)o(\alpha) を吐き続ける. 何か入力のシグナルを受け取るまでは状態 α\alpha であり続け、 入力 aa を受け取ると瞬時に状態を αa\alpha_a に買える. そうして o(αa)o(\alpha_a) を吐き続ける. 何の入力シグナルを受け取ったことのない時点での状態は ι\iota である.

他の有名な有限機械の形式化として、 Mealey machine があり、これは基本的には Moore machine と同様だが、 出力関数が o:S×IOo: S \times I \rightarrow O となっていて、やや複雑化されている. しかし実際これは、Moore machine と等価である. Moore machine において、状態 SSS×IS \times I に変えて、前回の入力を覚えておくことにすれば、模倣することが可能だからである.

本書は Kleene 理論を解説することが目的なので、それに当たって十分シンプルな Moore machine を有限機械として扱うのである.

状態遷移図

有限機械 MM について 状態遷移図 (state diagram) を書く. これは、状態をノード、遷移をエッジ (入力をエッジのラベルとする) と対応付けた有向グラフである. 例えば αa=β\alpha_a = \beta のとき、αaβ\alpha \rightarrow^a \beta という有向枝を加える.

ノードにはどの状態を対応付けたかを記すためのラベルを付与する. 通常、ラベルはただ単に状態の名前であるが、ここに出力 o(α)o(\alpha) も一緒に書いて α:o(α)\alpha:o(\alpha) と書く.

また、通常のノードは丸で囲んで記すが、初期状態に対応するノードは二重丸に囲むことにする.

出力が O(M)={0,1}O(M) = \{0, 1\} であるような機械をバイナリ機械 (binary machine) という. この場合には、ノードのラベル全てに ":0" ":1" を書かなくても 1 を出力するときにだけ ":1" を書くことにすれば、 書いてないものは ":0" だと分かるので、省略することにする.

次は状態を3つ持つバイナリ機械の例.

%3 α α β β α->β a γ:1 γ:1 α->γ:1 b β->γ:1 a β->γ:1 b γ:1->α b γ:1->γ:1 a

これは

  1. S(M)={α,β,γ}S(M) = \{\alpha, \beta, \gamma\}, I(M)={a,b}I(M) = \{a,b\}, O(M)={0,1}O(M) = \{0,1\}
  2. 初期状態は α\alpha
  3. t(α,a)=β,t(β,b)=γ,t(\alpha, a) = \beta, t(\beta, b) = \gamma, \ldots
  4. o(α)=o(β)=0o(\alpha) = o(\beta) = 0, o(γ)=1o(\gamma) = 1

といった機械である.

語法

語をいくつか用意する. 入力を有限個並べて出来る列を語 (word) という. すなわち入力全体 II に対して語全体は I*I^* である. 列の長さを語の長さ (length) という. 長さがゼロの語を許容する. これを空語 (empty word) といい、 11 と書く.

状態 α\alpha の状態に語 w=abkw = ab\ldots k を受け取るとは、入力 a,b,,ka, b, \ldots, k を逐次的に受け取ることである. t(α,a)t(\alpha, a)αa\alpha_a と書いていたが、これを語に拡張して αw=t(t(t(α,a),b),,k)\alpha_w = t(\ldots t(t(\alpha, a), b), \ldots, k) と書く. また出力関数を拡張して fα(w)=o(αw)f_\alpha(w) = o(\alpha_w) を定める.

自明に α1=α\alpha_1 = \alpha である.

状態 α\alpha からある語 ww を受け取って状態 β\beta に遷移するとき、β\betaα\alpha から到達可能 (accessible) である、という. 初期状態 ι\iota から到達可能のとき、単にβ\beta は到達可能だという.

2つの状態 α\alpha, β\beta について、任意の語 ww を以って o(αw)=o(βw)o(\alpha_w) = o(\beta_w) が常に成り立つとき、 α\alphaβ\beta とは区別不能 (indistinguishable) であると言い、 其の逆、即ち、ある語によって出力が異なるとき、区別可能 (distinguishable) であるという.

2つの機械 MM, MM' について、それぞれ入力と出力が同じ領域であって (I(M)=I(M)I(M)=I(M'), O(M)=O(M)O(M)=O(M'))、 MM の状態 α\alphaMM' の状態 β\beta とを適当に対応付けることで、区別不能にできるとき、 MMMM' は同じ挙動である (have same console) という.

しばしば、ある特定の挙動をする機械は複数ありえる中で、単純な機械を設計することが目的となるため、この概念が重要となる.

区別不能性による商 (quotrient by indistinguishablity)

機械 MM から次の手順に依って M÷M^{\div} を構成することを考える.

  1. MM の状態 α\alpha に対して MM の中で α\alpha と区別不能な状態のクラスを α\bar{\alpha} と書いてこれを MM' の状態とする (区別不能に関する商集合)
  2. I(M)=I(M)I(M') = I(M), O(M)=O(M)O(M') = O(M)
  3. MM' の遷移関数 ttt(α,a)=βt(\bar{\alpha}, a) = \bar{\beta} where t(α,a)=βt(\alpha, a) = \beta で定める
  4. o(α)=o(α)o(\bar{\alpha}) = o(\alpha)
  5. ι\bar{\iota} を初期状態とする

M÷M^\divMM と区別不能.

Example

次の機械 MM を考える. 入力はただ一つしかないとして略す.

%3 α:1 α:1 β β α:1->β γ:1 γ:1 β->γ:1 δ δ γ:1->δ ε:1 ε:1 δ->ε:1 ε:1->β ζ ζ ζ->ε:1 η η η->η

例えば β,δ\beta, \delta は区別不能であることが確認できる. 結局、M÷M^\div は次のようになる.

%3 α:1 α:1 β β α:1->β η η η->η

到達可能性による切り捨て (truncation by accessiblity)

機械 MM に対して次のようにして MM^- を構成する.

  1. MM の初期状態 ι\iotaMM^- の初期状態
  2. MM において ι\iota から到達可能な状態全てが MM^- の状態
  3. 遷移関数はそのままだが、MM^- にもある状態に制限
  4. 出力関数も同様に制限

やはりこの MM^-MM と区別不能である.

Example

先ほどの MM を用いれば MM^- は次のようになる.

%3 α:1 α:1 β β α:1->β γ:1 γ:1 β->γ:1 δ δ γ:1->δ ε:1 ε:1 δ->ε:1 ε:1->β

ちょうど、ζ,η\zeta, \eta が消え、そこに入る、または出る枝が削除されたものになる.

極小機械 (minimal machine)

機械 MM が極小であるとは、全ての状態が到達可能で、全ての状態が区別可能であることを言う.

また、2つの機械 M,NM, N が同じ挙動 (behavior) であるとは、初期状態が同じで、状態遷移図についてグラフ同型であることを言う.

Thm. 3

M÷M^{-\div} 及び M÷M^{\div -} は極小機械であって同じ挙動をする.