このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

状態遷移

 入力とそのときの内部状態に依存して状態が変化することを状態遷移という。 状態遷移の様子を、有向グラフで図示したものを状態遷移図という。

 また、有限の状態を制御するモデルに、オートマトン(automaton)がある。オートマトンのうちで最も単純なモデルが、有限オートマトンである。

有限オートマトン

 有限(状態)オートマトン(FNA:Finite Automaton)はO (n)で解析できるため大変素性のよい言語モデルである。しかしながら、それだけに記述能力はあまり高くなく、そのため比較的単純なモデルのみに使われる。

 有限オートマトンは入力テープ・有限状態制御装置・読み取りヘッドから構成され、出力はない単純なオートマトンである。テープは入力だけで出力がないため、最も単純な機械(モデル)である。

有限オートマトンの分類

 有限オートマトンは決定性(deterministric)のものと非決定性(noddeterministric)のものがある。決定性オートマトンとはあいまいさがないオートマトンである。

決定性有限オートマトン

[定義]
決定性有限オートマトンとは次の5組のことをいう。
M=(K,Σ,δ,q0,F)
・K:空でない有限集合。Kの要素は状態(state)と呼ばれる。
・Σ:アルファベット
・δ:K×Σ→Kの遷移関数
・q0:初期状態(q0∈K)
・F:最終状態(F⊆K)
ちなみに、δを次の(1)(2)によって、K×Σ*→Kへの関数に拡張する。
(1)δ(q,ε)=q (q∈K)
(2)δ(q,ax)=δ(δ(q,a),x)
(q∈K、a∈Σ、x∈Σ*

 状態には、受理状態と非受理状態の2つの区分がある。入力テープから1文字読み取るごとに状態を変化させ、入力文字列が終わったときの状態が受理状態ならば入力を「受理する」、そうでなければ入力を「受理しない」という。

[定義]
語w∈Σ*はδ(q0,w)∈Fであるとき、有限オートマトンMによって受理される(accepted)という。

 「受理する」・「受理しない」の様子は、状態遷移図で表すことができ、受理状態は◎印の接点で図示する。受理の判断は、初期状態から入力をたどり、受理状態で停止するか否かでおこなう。

有限オートマトンの例

例1:

例2:δ(q,a)=rは次を表す。

 遷移表が次のように与えられているとします。

δab

|q0|q1|q2|

q1q2q0
q2q2q2

 この遷移表から状態図を導いてみます。

 ちなみに、2重丸は終点を意味します。

 この有限オートマトンによって、語(w=)abaは拡張されたδに従って次のようになる。

δ(q0,aba)
=δ(δ(q0,a),ba)
=δ(q1,ba)
=δ(δ(q1,b),a) =δ(q1,a)
=q1
∈F

∴wはMによって受理される。

参考文献

  • 『図解雑学 コンピュータ科学の基礎』
  • 『平成16年度【秋期】基本情報技術者合格教本』