例2.2
正則集合X=(ab*a)*を受理する有限オートマトンM=(Q,Σ,δ,q0,F)を構成しよう。
いや、いきなりソレはついていけないので、もっと単純なものにしよう。
Σ={日本語のひらがな}、正則集合X={「あい」}⊆Σ*としよう。2文字からなる語1つだけでも正則集合だ。
定理2.1の証明にしたがって構成する。
Xの商のなす集合、
Q={x\X|x∈Σ*}
={あ\X,い\X,…,ん\X,ああ\X,あい\X,…,あああ\X,…}
であるが、「アタマに何かくっつけたら『あい』になるもの」は、
- 「『あ』をくっつけて『あい』になる【い】」
- 「『あい』をくっつけて『あい』になるε」
- 「εをくっつけて『あい』になる【あい】」
だけだ。だから、
Q={{「あい」},{「い」},{ε}}
これは元が3つの有限集合だ。このQを状態の集合と考える。
状態遷移関数 δ(x\X,a)=xa\X も例示してみよう。
x\X={「あい」}∈Qの場合、x=εであった。
a=「あ」とすると、
δ(x\X,a)=εa\X=あ\X={「い」}.
a≠「あ」のときは、
δ(x\X,a)=εa\X=い(etc)\X=φ. ∵「い」などをアタマにくっつけたとき「あい」になるひらがな語は存在しないから。
x\X={「い」}∈Qの場合、x=「あ」であった。
a=「い」とすると、
δ(x\X,a)=あい\X={ε}.
a≠「い」のとき(たとえば「う」)は、
δ(x\X,a)=あ・う(etc)\X=φ.
x\X={ε}∈Qの場合、x=「あい」であった。
aがなんであれ(たとえば「う」)、
δ(x\X,a)=あい・う(etc)\X=φ.
初期状態は ε\X={「あい」} とする。
受理状態の集合は F={y\X|y∈X}
={y\X|y∈{「あい」}}
={あい\X}
={ε}
とする。
図にするとこうなる?
状態の集合には空集合を含めて、 Q={{「あい」},{「い」},{ε},φ} としなければいけないのかな。
状態遷移関数の例を見ながら図にしてみたのだが、空集合に対してもδ(φ,a)を考えなければいけないハメに。そうでないと図の一番下の矢印部分が説明できないし。
x\X=φ であるときのxって何だ? 「あい」,「あ」,ε以外の全てか。ならば、x=「えお」とでもして考えよう。
aがなんであれ(たとえば「う」)、
δ(x\X,a)=えお(etc)・う(etc)\X=φ
というのは自明か。「えお・う」などをアタマにくっつけたとき「あい」になるひらがな語は存在しないから。
これでつじつまが合いそうだということは、やはり Q={{「あい」},{「い」},{ε},φ} が正解なんだろう。
One Comment