非決定性オートマトンのシミュレーション

非決定性オートマトンがあり、それがある語を受理するかどうかを調べたいとき、方法はいくつかあります。オートマトンを決定性オートマトンに変換してもよいし、何とかして試してみることもできます。また、NFA の動作をシミュレートするアルゴリズムを使うこともできます。

アルゴリズムの考え方

考え方を、例を使って具体的に見てみましょう。次のオートマトンを考えます。

これはある言語を受理する非決定性有限オートマトンです。どんな言語かは、今は気にしなくてかまいません。このオートマトンの、入力語11001に対する計算がどうなるかを見ていきます。考え方は次のとおりです。語から記号を1つ処理し、同じ記号に対する複数の遷移によって進める先をすべて調べます。これらの状態をすべて覚えておき、次のステップでは「これらの状態すべてに同時にいる」と考えて、そこからさらにどこへ進めるかを調べます。

そこで、今いる可能性のある状態の集合と、語のまだ読んでいない部分を覚えておきます。はじめは組 ⟨{q₀}, 11001⟩ です。状態 q₀（初期状態）から始め、入力は語11001です。オートマトンは次のようになります。今いる状態を赤の太線で強調しています。

最初の記号は1です。状態 q₀ からは記号1の遷移が1本しかないので、状態 q₁ に移ります。組 ⟨{q₁}, 1001⟩ を覚えておきます。オートマトンは次のようになります。

先に進みましょう。語のまだ読んでいない部分は1001なので、再び1の遷移を探します。今度は2本あり、状態 q₀ にもどる遷移と、状態 q₃ に進む遷移です。ここでは両方の状態に同時に進みます。そこで、組 ⟨{q₀, q₃}, 001⟩ を覚えておきます。

なぜこうするのでしょうか。初期状態から語11によって、状態 q₃ にも状態 q₀ にも行ける道があることはわかっています。どちらの枝が役に立つかはまだわからないので、とにかく両方を覚えておくのです。先に進みましょう。入力は記号0です。今度は、q₀ からの遷移と q₃ からの遷移の両方を見なければなりません。状態 q₀ からは状態 q₁ と q₂ への遷移が、状態 q₃ からは q₁ にもどる遷移が出ています。これらの状態をすべて集めると、組 ⟨{q₁, q₂}, 01⟩ が得られます。

しかし、このステップはまだ終わっていません。状態 q₂ から状態 q₄ への ε 遷移があります。ε 遷移は、次の文字を読まずに「いつでも進める」のでした。言いかえると、入力語から次の記号を読まずに、さらに状態 q₄ に移ることができます。そこで、今いる可能性のある状態に状態 q₄ を加えて、⟨{q₁, q₂, q₄}, 01⟩ とします。オートマトンに色をつけると、次のようになります。

次の入力は0です。今いる3つの状態から、どこへ移れるかを調べます。q₁ からは0の遷移がないので、どこへも移れません。この枝の計算はここで終わります。状態 q₄ からも、どこへも進めません。状態 q₂ からは、状態 q₂ にもどります。しかし、状態 q₂ からは再び状態 q₄ への ε 遷移が出ているので、状態 q₄ にも進めます。したがって、状態の集合 {q₁, q₂, q₄} からは、記号0によって状態の集合 {q₂, q₄} に進めます。こうして組 ⟨{q₂, q₄}, 1⟩ が得られます。

最後に、入力は記号1です。状態 q₂ からはどこへも進めないので、この枝の計算はここで終わります。一方、状態 q₄ からは状態 q₃ と q₅ に進めます。組 ⟨{q₃, q₅}, ε⟩ が得られます。

これでオートマトンは語全体を読み終え、2つの状態 q₃, q₅ に「いる」ことになります。そのうち少なくとも1つは受理状態なので、オートマトンは語11001を受理します。

アルゴリズム

まず、状態の集合を引数にとり、そこから ε 遷移によってさらにどの状態に進めるかを計算する関数が必要です。入力はオートマトン ⟨Q, Σ, δ, q₀, F⟩ と状態の集合 States で、出力はこれらの状態に、ε 遷移で進める状態を加えた集合です。この操作を、集合 States の ε 閉包といいます。

$\begin{aligned} Function E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, S t a t e s) \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup {q} \cup δ (q, ε) \\ EndFor \\ If N e x t S t a t e s ∖ S t a t e s = \emptyset Do \\ Return S t a t e s \\ Else \\ Return E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ EndIf \\ EndFunction \end{aligned}$

この関数を、非決定性オートマトンの動作をシミュレートする関数の中で使います。入力はオートマトン、入力語 w = w₁w₂… w_n、そしてオートマトンが今いる状態の集合です。出力は、オートマトンがその語を受理するかしないかに応じて、YES か NO の答えです。

$\begin{aligned} Function C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w, S t a t e s) \\ If w = ϵ Do \\ If S t a t e s \cap F \neq \emptyset Do \\ Return YES \\ Else \\ Return NO \\ EndIf \\ EndIf \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup δ (q, w_{1}) \\ EndFor \\ N e x t S t a t e s \leftarrow E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ Return C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w_{2} w_{3} \dots w_{n}, N e x t S t a t e s) \\ EndFunction \end{aligned}$

オートマトンが語 w を受理するかどうかを調べたいときは、関数を ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})) のように呼び出します。

参考文献

章: 有限オートマトン, 完全なオートマトン, 非決定性有限オートマトン, 非決定性オートマトンのシミュレーション, NFA から DFA への変換

« 前へ: 非決定性有限オートマトン

次へ: NFA から DFA への変換 »