そういうわけで、

定理2.3
有限オートマトンの受理集合は正則集合である。

が証明された。
　この定理を「集合に関する連立方程式」の考え方で証明する方法が載っている。

有限オートマトンM＝(Q,Σ,δ,q₀,F)に対して、Q={1,2,…,n}、
L_i＝{x∈Σ^＊｜δ^＊(i,x)∈F}　（i=1,2,…,n）
とおく。i＝q₀のときL_i＝L(M)である。

　今度はL_ijkは考えない。

このL₁,L₂,…,L_nについて、次の（１）～（４）が成り立つ。

• （１）
  L_i＝∪_{(j=1 to n)}A_ij・L_j　∪　B_i　（i＝1,2,…,n）
  ただし、A_ij＝{a∈Σ｜δ(i,a)＝j}、B_i＝{ε｜i∈F}

  　なお、∪の上下に変数の範囲を書くことが困難なので、下付き文字として(j=1 to n)と記した。

• （２）
  もし　X₁,X₂,…,X_n⊆Σ^＊が、上記のA_ij,B_iに対して
  　X_i＝∪_{(j=1 to n)}A_ij・X_j　∪　B_i　（i＝1,2,…,n）　…※
  を満たすならば、L_i⊆X_i　（i=1,2,…,n）　である。
  つまりL₁,L₂,…,L_nは上のn個の連立方程式※の最小解である。

  　連立方程式を満たす集合X_iがあるとすると、必ずその中にL_iを含んでいる、ということは、その連立方程式を満たす集合のうちではL_iが一番小さい、ということだ。

• （３）
  任意のA_ij,B_iに対して、連立方程式※の最小解X^～₁,X^～₂,…,X^～_nは以下のように求められる。
  n＝1のとき、X^～₁＝A₁₁^＊・B₁.
  n＞1のときは次のように考える。
  連立方程式の第n式を
  X_n＝∪_{(j=1 to n)}A_nj・X_j　∪　B_n
  　＝A_nnX_n　∪　(∪_{(j=1 to n-1)}A_nj・X_j　∪　B_n)
  とし、X₁,…,X_n-1を単なるパラメータとみなせばn＝1の場合と同様に変形できる。すなわち、
  　X_n＝A_nn^＊・(∪_{(j=1 to n-1)}A_nj・X_j　∪　B_n).
  これを、第1～n-1式に代入し、X₁,…,X_n-1に関する連立方程式
  　X_i＝∪_{(j=1 to n-1)}A’_ij・X_j ∪　B’_i　（i＝1,2,…,n-1）
  　ただし、A’_ij＝A_ij∪A_in・A_nn^＊・A_nj、B’_i＝B_i∪A_in・A_nn^＊・B_n　（i,j=
  1,2,…,n－1）
  が得られる。このn－1元連立方程式の最小解を　X^～₁,X^～₂,…,X^～_n-1　とすると、もとのn元連立方程式の最小解は　X^～₁,X^～₂,…,X^～_n-1,X^～_n　である。
  　ただし、X^～_n＝A_nn^＊・(∪_{(j=1 to n-1)}A_nj・X^～_j　∪　B_n)

  n-1元連立方程式の最小解がわかっている前提で、　n元連立方程式の最小解もわかると。

• （４）
  Aij,Biがすべて正則集合なら、（３）で求めた各X^～_iは正則集合である。

　（３）の手順をきちんと把握したい。字面ではわかるけど…