省略してしまった証明部分を再読。あとあと効いてきそうなので書いておく。
各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の定義による。