この節では任意の正則集合に対してそれを受理する有限オートマトンが存在することを示す。
任意の正則集合、とは、語の集合で変態的でないもの、程度に考えておこう。つまり、たいていの語の集合について、ある語がその集合に属するか否かを有限の手順で判別できるはずだ、ということかな。
XをΣ上の正則集合、Xの商のなす集合を Q={x\X|x∈Σ*} とおく。Qは有限集合である。
このQを状態の集合とする。
状態遷移関数 δ:Q×Σ→Q を次のように定義する。
δ(x\X,a)=(xa)\X ( x∈Σ*,a∈Σ)
ややこしいが、Qは集合の集合、高校数学で「族」と習ったものになっている。
状態遷移関数 δ:Q×Σ→Q を δ*:Q×Σ*→Q に拡張する。
δ*(x\X,y)=(xy)\X ( x∈Σ*,y∈Σ*)
|y|=n,y=a1a2…an とおけば、
δ*(x\X,y)=δ(δ(…δ(δ(x\X,a1),a2)…),an)=a1a2…an\X
ということだ。
特に x=ε のとき δ*(ε\X,y)=y\X である。このことに注意して、Qの元ε\Xを初期状態q0とし、受理状態の集合Fを
F={y\X|y∈X}
とおいて有限オートマトン M=(Q,Σ,δ,q0,F) を構成する。
そうすると、
y∈L(M) ⇔ δ*(ε\X,y)∈F ⇔ y\X∈F ⇔ y∈X
∴ L(M)=X.
こうしてXを受理するオートマトンが構成できた。
ここだけ日本語に直しておこう。
「ある語yがオートマトンMによって受理される」 とは、
「『初期状態からはじめてyを1文字ずつ与えていった結果(δ*)』が受理状態の一つである」 ということであり、それは、
「『yをアタマにくっつけたときにXの元になるような語の集合』が受理状態の一つである」 ということと同じで、それはFの定義によれば、
「yがXの元である」ということと同じなのだ。
定理2.1
任意の正則集合Xに対して、Xを受理する有限オートマトンが存在する。
y\X∈F ⇔ y∈X の部分について、
(最後の2式が同値なことは、y∈X かつ y\X=y’\X ならば ε∈y\X=y’\X, よってy’∈X であることによる)
…と注が付いているが、却って訳がわからず。
Pingback: 有限オートマトン2-2.正則集合と有限オートマトン(1) その2 | デザイナーの数学