NFA から DFA への変換

非決定性オートマトンを決定性オートマトンに変換する方法を見ていきます。これによって、非決定性オートマトンと決定性オートマトンの計算能力が等しいことが示されます。

基本的な考え方

ε 遷移のない非決定性オートマトン ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ を考えます。決定性オートマトン ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ を、次のようにつくります。

Q_D ⊆ 2^Q_N
Σ_D = Σ_N
p₀ = {q₀}
F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

遷移関数 δ_D は、次のように定義します。

$\forall Q \in Q_{D}, a \in Σ_{D} : δ_{D} (Q, a) = ⋃_{q \in Q} δ_{N} (q, a)$

これはどういう意味でしょうか。非決定性オートマトンは同時に複数の状態にいることができるので、例えば非決定性オートマトンが状態 {q₀, q₁} にいる場面が起こりえます。次の記号、例えば1を読むと、状態の集合 {q₀, q₂, q₃} に進むことがあります。同じオートマトンの決定性版では、これを次のように表します。2つの状態をつくり、それらに {q₀, q₁} と {q₀, q₂, q₃} という名前をつけ、その間に記号1の遷移を引きます。形式的には1つの状態から別の1つの状態に移るだけですが、名前のおかげで、非決定性オートマトンならそれぞれ2つ、3つの状態にいたはずだとわかります。

例

次の非決定性オートマトンを考えます。

決定性オートマトンをつくるには、何よりもまず新しい遷移関数をつくる必要があります。そのために、すべての遷移を書きこむ表を使います。はじめは、表は次のようになります。

$\begin{array}{ccc} 状態 / 記号 & 0 & 1 \\ {q_{0}} \end{array}$

アルゴリズムが終わったとき、左の列には決定性オートマトンのすべての状態が並びます。そして、埋め終わった表が遷移関数を定めます。では、状態 {q₀} にいて入力が記号0と1のとき、どの状態に進むかを表に書きこみます。

$\begin{array}{ccc} 状態 / 記号 & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \end{array}$

状態 q₀ からは、記号0の遷移は状態 q₁ だけに向かい、記号1の遷移は状態 q₁ と q₂ に向かいます。ここで、表に2つの新しい状態 {q₁} と {q₁, q₂} を加えます。なぜでしょうか。表に書きこんだ状態の集合がまだ左の列にないときは、その状態の集合を左の列に加えるからです。

$\begin{array}{ccc} 状態 / 記号 & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \\ {q_{1}} \\ {q_{1}, q_{2}} \end{array}$

そして、再び表を埋めます。状態 {q₁, q₂} については、両方の状態を調べるのを忘れないようにしましょう。つまり、状態 q₁ から進める状態と、状態 q₂ から進める状態の和集合をとります。

新しい状態がいくつか得られたので、表に加える必要があります。

…そして、再び遷移を書きこみます。

$\begin{array}{ccc} 状態 / 記号 & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \\ {q_{1}} & {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{3}} \\ {q_{1}, q_{2}} & {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{3}} \\ {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{1}, q_{2}, q_{3}} \\ {q_{0}, q_{3}} & {q_{1}} & {q_{1}, q_{2}} \end{array}$

状態 {q₀, q₁, q₃}、{q₁}、{q₁,q₂} はすでに表にあるので、状態 {q₀,q₁,q₂,q₃} だけを加えます。

新しい状態はもう加わらなかったので、表は完成です。あとは状態遷移図をかくだけです。決定性オートマトンの状態は1列目に、記号0と1の遷移はその右の列にあります。もとのオートマトンの受理状態を含む状態は、どれもこのオートマトンでも受理状態になります。つまり、q₃ を含む状態はすべて受理状態です。オートマトンは次のようになります。

このオートマトンが本当に正しく動くことを確かめてみましょう。語11001を受理するか試します。決定性オートマトンでは、次の道をたどります。

$q_{0} \to^{1} q_{1}, q_{2} \to^{1} q_{0}, q_{3} \to^{0} q_{1} \to^{0} q_{0}, q_{1}, q_{3} \to^{1} q_{0}, q_{1}, q_{2}, q_{3}$

最後の状態 {q₀, q₁, q₂, q₃} は受理状態なので、オートマトンはこの語を受理します。非決定性オートマトンでも、シミュレーションの途中で同じ状態にたどり着きます。つまり、状態 q₀ から始め、記号1で状態 {q₁, q₂} に進みます。次の記号1で状態 {q₀,q₃} に進み、残りの記号についても同様です。最後には状態 {q₀, q₁, q₂, q₃} のすべてにいることになり、オートマトンはこの語を受理します。

参考文献

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

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

次へ: オートマトンの最小化 »