有限オートマトン2-3.正則集合と有限オートマトン（２） その４
そういうわけで、 定理2.3 有限オートマトンの受理集合は正則集合である。 が証明された。 この定理を「集合に関する連立方程式」の考え方で証明する方法が載っている。 有限オートマトンM＝(Q,Σ,δ,q0,F)に対し […]
有限オートマトン2-3.正則集合と有限オートマトン（２） その３
省略してしまった証明部分を再読。あとあと効いてきそうなので書いておく。 各i,k∈Qに対して Aik＝{a∈Σ｜δ(i,a)＝k} とおく。 つまり、「状態iのときに与えられたら状態kになるような1文字『a』の集合 […]