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

この節では、初めに前節の定理の逆、すなわち有限オートマトンの受理集合が正則集合であることを示し、次いで有限オートマトンの拡張である日決定性有限オートマトンと有限遷移図について述べる。

有限オートマトン M=(Q,Σ,δ,q0,F) の状態の集合を {1,2,…,n} とする(状態の名称そのものは本質的でないため、このように仮定しても一般性を失わない)。

 ああ、やっぱり状態の名称はたんなるラベルと考えていいのだな。

このQの各元i,j,kに対して
Lijk
 {a1a2…am
  a1,a2,…,am∈Σ,m≧1,
  δ(i,a1a2…al)≦j (l=1,…,m-1),
  δ(i,a1a2…am)=k}
 ∪
 {ε|i=k}
とおく。

 一目で理解できたらすごいぞ、これ。日本語訳はのちほど。

 さて、Lijkの定義を日本語訳してみよう。

 Mによって受理される語の集合であって、3つの状態i,j,kによって決まるものを、次のとおり定める。(ここまで左辺)
 それは、m文字からなる語の集合であり、(ここまで右辺の1行目)
 当然各文字はΣの元であり、1文字以上である(つまりεではない)とする。(ここまで右辺の2行目)
 その語の条件として、状態iから始めて、その語を何文字目かまで読んだ状態がj以下にとどまるような語でなければならない。(ここまで右辺の3行目)
 また、状態iから始めて、その語を全て(m文字目まで)読んだ状態がkであるような語である。(ここまで右辺の4行目)
 …というような集合と、次の集合――
 ――iとkが同じ状態であるときはεだけからなる集合――を合わせたもの(右辺の5、6行目。和集合の演算)
  をLijkとする。
 こんな感じだろうか?

Lijkは、jより大きい番号の状態を経由せずに、状態iからkへ達する入力語の集合である。特にj= nの場合、Linkは状態iからkに至る全ての入力語の集合である。

 nがどこから出てきたかと言うと、Q={1,2,…,n}だったからね。
 なんだか i≦j≦k と、暗黙のうちに置いているような気がして気持ち悪い。単なるラベルだし、Mが一直線に並んでいるとも限らない…。ただ、j= nのLinkを考えるためだけなら、問題にならないかな。

したがって、Mの受理集合は
 L(M)=∪{Link|k∈F} (ただし i=q0
と表される。

 ここまで、どうにか理解。


Want to Leave a Reply?