そういうわけで、
定理2.3
有限オートマトンの受理集合は正則集合である。
が証明された。
この定理を「集合に関する連立方程式」の考え方で証明する方法が載っている。
有限オートマトンM=(Q,Σ,δ,q0,F)に対して、Q={1,2,…,n}、
Li={x∈Σ*|δ*(i,x)∈F} (i=1,2,…,n)
とおく。i=q0のときLi=L(M)である。
今度はLijkは考えない。
このL1,L2,…,Lnについて、次の(1)~(4)が成り立つ。
- (1)
Li=∪(j=1 to n)Aij・Lj ∪ Bi (i=1,2,…,n)
ただし、Aij={a∈Σ|δ(i,a)=j}、Bi={ε|i∈F}なお、∪の上下に変数の範囲を書くことが困難なので、下付き文字として(j=1 to n)と記した。
- (2)
もし X1,X2,…,Xn⊆Σ*が、上記のAij,Biに対して
Xi=∪(j=1 to n)Aij・Xj ∪ Bi (i=1,2,…,n) …※
を満たすならば、Li⊆Xi (i=1,2,…,n) である。
つまりL1,L2,…,Lnは上のn個の連立方程式※の最小解である。連立方程式を満たす集合Xiがあるとすると、必ずその中にLiを含んでいる、ということは、その連立方程式を満たす集合のうちではLiが一番小さい、ということだ。
- (3)
任意のAij,Biに対して、連立方程式※の最小解X~1,X~2,…,X~nは以下のように求められる。
n=1のとき、X~1=A11*・B1.
n>1のときは次のように考える。
連立方程式の第n式を
Xn=∪(j=1 to n)Anj・Xj ∪ Bn
=AnnXn ∪ (∪(j=1 to n-1)Anj・Xj ∪ Bn)
とし、X1,…,Xn-1を単なるパラメータとみなせばn=1の場合と同様に変形できる。すなわち、
Xn=Ann*・(∪(j=1 to n-1)Anj・Xj ∪ Bn).
これを、第1~n-1式に代入し、X1,…,Xn-1に関する連立方程式
Xi=∪(j=1 to n-1)A’ij・Xj ∪ B’i (i=1,2,…,n-1)
ただし、A’ij=Aij∪Ain・Ann*・Anj、B’i=Bi∪Ain・Ann*・Bn (i,j=
1,2,…,n-1)
が得られる。このn-1元連立方程式の最小解を X~1,X~2,…,X~n-1 とすると、もとのn元連立方程式の最小解は X~1,X~2,…,X~n-1,X~n である。
ただし、X~n=Ann*・(∪(j=1 to n-1)Anj・X~j ∪ Bn)n-1元連立方程式の最小解がわかっている前提で、 n元連立方程式の最小解もわかると。
- (4)
Aij,Biがすべて正則集合なら、(3)で求めた各X~iは正則集合である。
(3)の手順をきちんと把握したい。字面ではわかるけど…