有限オートマトン2-2.正則集合と有限オートマトン(1) その2

例2.2
正則集合X=(aba)を受理する有限オートマトン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 Response to “有限オートマトン2-2.正則集合と有限オートマトン(1) その2”

  1. 1
    admin

    例2.2を素直にやった方がアルファベットがa,bの2つしかないから簡単だったかも。


Want to Leave a Reply?