有限オートマトン2-3.正則集合と有限オートマトン(2) その3

 省略してしまった証明部分を再読。あとあと効いてきそうなので書いておく。

各i,k∈Qに対して
 Aik={a∈Σ|δ(i,a)=k}
とおく。

 つまり、「状態iのときに与えられたら状態kになるような1文字『a』の集合」がAik

そのとき、j=1に対するLijkは、iから途中1(=j)だけを経由してkに至る際の入力語の集合であるから、
 Li1k=Ai1・A11・A1k ∪ Aik ∪ {ε|i=k} (i,k∈Q)
と表せ、これはΣ上の正則集合である。

 ここが帰納法のswitch(j){case 1:…の部分だ。
 Lijkが、直前に定義したAを用いて、
 「iから1に遷移する文字の集合」「1から1に遷移する文字の集合、任意個の積(任意個だからなくてもよい)」「1からkに遷移する文字の集合」の積
  または(つまり和集合)、
 「iから直接kに遷移する文字の集合」
  または、
 「行き先のkが出発点のiと同じときは空語だけからなる集合(遷移する必要がないから)」
 と書けるといっている。
 ここに登場する個々の集合は{a|a∈Σ}(←これは正則集合だ)の和集合として書けるから、それらの和集合であるLijkも正則集合だ。

 case j>1:…はまた今度。

 続けます。

帰納法の仮定としてLi(j-1)kが正則集合であるとする。
 Lijk=Li(j-1)j・Lj(j-1)j・Lj(j-1)k ∪ Li(j-1)k
であるから、Lijkもまた正則集合である。

 個別の集合が何を意味するのかは、j=1の場合と同じように考えればいいだろう。あれ? なんで最後に ∪{ε} がついてないのかな? あ、そうか。
 {ε|i=k}は、末尾のLi(j-1)kにすでに含まれているんだ。∵Lijkの定義による。


Want to Leave a Reply?