非決定性有限オートマトン

これまでの章で紹介した有限オートマトン（DFA と略します）は、どれも決定性でした。つまり、どの時点でもオートマトンが何をするかがはっきり決まっていました。ここでは、もっと一般的な非決定性有限オートマトン（NFA と略します）という概念を見ていきます。NFA には、同じ状態から出て同じ記号に対応する遷移が複数あってもかまいません。

例

次のオートマトンの状態遷移図を見てみましょう。

この図のどこが変わっているでしょうか。ノード q₀ から、記号0の辺が2本出ていることです。そのため、語001を受理しようとすると、オートマトンは状態 q₀ にとどまるべきか、q₁ への遷移に従うべきかがわからないように見えます。このようなオートマトンが非決定性のオートマトンです。

ここでいう決定性とは、どの場面でもオートマトンが何をするかがはっきりしていて、あいまいさがないことです。決定性オートマトンには、各状態と各記号について遷移が1つしかありません。非決定性とはあいまいさがあることで、1つの状態から同じ記号について、例えば3本の遷移が出ていてもかまいません。

では、オートマトンはどうやって選ぶのでしょうか。非決定性オートマトンは、可能であれば、いつでも語を受理することにつながる遷移を選びます（「当てる」ということもあります）。

オートマトンに語001を入力すると、オートマトンがこの語を処理する方法には次のものがあります。

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

これに、語を全部は読まない場合が加わります。1つ目では、オートマトンはずっと状態 q₀ にとどまっていました。遷移の規則がそれを許しているので、これはもちろんかまいません。2つ目の枝では、思い切ってほかの状態に進み、最後に受理状態である状態 q₂ にたどり着きました。この枝なら、オートマトンは語を受理します。非決定性オートマトンは、語を受理する枝があれば、いつでも自動的にその枝を選びます。

どうやって「都合のよい」枝を自動的に選ぶのでしょうか。非決定性オートマトンはすべての可能な枝をたどり、語を受理する枝が見つかれば語を受理する、と考えることができます。すべての枝をどうやってたどるのでしょうか。簡単にいえば、今の記号に対して n 本の辺が出ている状態にいるとき、オートマトンは自分自身を n 個に複製し、それぞれの複製が別の道を進みます。こうして、すべての可能性を順にたどることになります。

オートマトンの計算の木による表現

先ほどのオートマトンを少し変えてみます。

非決定性は最初の状態に残っています。前のオートマトンは、01で終わるすべての語を受理しました。この変更したオートマトンは、部分語01を含むすべての語を受理します。例えば、語101や0101を受理します。計算のすべての枝は、木を使えば簡単に図に表せます。例えば、語01010の木は次のようになります。

はじめは初期状態 q₀ にいます。入力は語01010で、最初のまだ読んでいない文字は0です。状態 q₀ からは、記号0の遷移が2本、状態 q₀ と q₁ に出ています。そのため、木のこのノードには子が2つ、q₀ と q₁ があります。次に記号1を読みます。ここにはあいまいさはなく、それぞれ状態 q₀ と q₂ に移ります。次に文字0を読むと、左の枝で再びあいまいさが生じるので、計算をさらに2つの枝に分けます。一方では再び q₀ にとどまり、もう一方では q₁ に進みます。以下同様です。

全部で2本の枝が、受理状態である状態 q₂ で終わっていることに注目しましょう。オートマトンがこの語を受理できる計算の枝が2本あるということです。したがって、このオートマトンは語01010を受理します。語1000についても、同じような木をつくってみましょう。

計算は状態 q₀ にとどまるか、状態 q₁ に移ります。しかし、そこから先へは進めません。入力には0しか残っておらず、状態 q₁ には記号1の遷移しかないからです。受理状態で終わる計算の枝が1本もないので、オートマトンは語1000を受理しません。

ε 遷移

非決定性オートマトンでは、さらに ε 遷移も使えます。ε 遷移とは、入力の記号が何であっても、語から記号を1つも読まずに行える遷移のことです。空語、1だけからなるすべての語、そして (10)ⁿ の形の語、つまり10、1010、…を受理する非決定性オートマトンは、どのように書けばよいでしょうか。

オートマトンを2つの「部分オートマトン」に分けました。上の部分は1からなる語を見分け、下の部分は (10)ⁿ の形の語を見分けます。語111を受理するか試してみましょう。オートマトンは、はじめは状態 q₀ にいて、入力は語111です。ε 遷移が使えるので、都合に応じて状態 q₁ か q₂ に移ることを選べます。ここでは状態 q₁ に移るのが都合がよいことがわかります。オートマトンはそこへ移ります。このとき、入力はまだ語111のままです。ここで初めて語の記号を読み始め、状態 q₁ から再び q₁ へと移っていき、語全体を読み終えて語を受理します。

1010を受理するか試すと、オートマトンははじめに状態 q₂ に移り、そこから記号を処理し始めて、やはり語を受理します。

語1100については、オートマトンが何をしても、この語を受理する方法はありません。

ε 遷移と非決定性は、多くの場面で作業を楽にしてくれます。例えば、正規言語の和集合がまた正規言語になることの証明は、ε 遷移を使うと、決定性有限オートマトンの場合よりずっと簡単に書けます。その証明では、次のオートマトンの例を使いました。

と

そして、両方の言語の和集合を受理する決定性有限オートマトンをつくりました。ε 遷移を使えば、このようなオートマトンは次のようにつくれます。

新しい初期状態を加え、そこからもとのオートマトンのもとの初期状態へ ε 遷移を2本引くだけです。オートマトンは、どちらの「部分オートマトン」で語を受理しようとするかを非決定的に選びます。

非決定性オートマトンの定義

決定性有限オートマトンと非決定性有限オートマトンの違いはすでに見たので、あとはそれを形式化するだけです。決定性有限オートマトンは5つ組 ⟨Q, Σ, δ, q₀, F⟩ として定義しました。ここで、Q は状態の集合、Σ はアルファベット、δ は遷移関数、q₀ は初期状態、F は受理状態の集合です。非決定性オートマトンの定義で変わるのは、遷移関数の定義だけです。

決定性の場合、δ(q, w) の値は1つの状態だけでした。一方、非決定性の場合は、1つの記号に対して複数の遷移が定義されていれば、値が複数の状態になることがあります。ε 遷移も定義する必要があるので、集合 Σ ∪ {ε} を集合 Σ_ε で表します。つまり、Σ_ε = Σ ∪ {ε} です。そして、関数 δ を次のように定義します。

$δ : Q \times Σ_{ε} \to 2^{Q}$

この 2^Q はべき集合、つまり集合 Q のすべての部分集合の集合を表します。計算の形式化は、有限オートマトンの場合ととてもよく似ています。オートマトンの様相は、やはり組 ⟨q, w⟩ ∈ Q × Σ^∗ です。計算のステップ ↦ は様相の集合上の関係で、

$⟨ q_{i}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{j}, w_{1} \dots w_{n} ⟩,$

が成り立つのは、q_j ∈ δ(q_i, w₀) であるとき、またそのときに限ります。定義のうえでいちばん大きく違うのはこの部分です。決定性オートマトンでは、関数 δ の値がいつも1つの状態だったので、この条件を q_j = δ(q_i, w₀) と書いていました。非決定性の遷移関数の値は状態の集合なので、記号 ∈ になっています。この関係の反射推移閉包も、やはり ↦ ^∗ で表します。オートマトンが語 w を受理するのは、次を満たす q_f ∈ F が存在するとき、またそのときに限ります。

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

参考文献

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

« 前へ: 完全なオートマトン

次へ: 非決定性オートマトンのシミュレーション »