オートマトンの最小化

オートマトンの最小化とは、状態の数ができるだけ少ない等価なオートマトンを見つけることです。冗長な状態を1つも含まないオートマトンでも、さらに簡単にできることがあります。

例

次のオートマトンを考えます。

このオートマトンが受理するのは、語01と11だけです。同じ言語を受理する、状態が3つのもっと簡単なオートマトンがあることは明らかです。状態 q₁ と q₂ を1つの新しい状態 {q₁, q₂} にまとめ、状態 q₁ または q₂ に向かっていた遷移は、新しい状態に向かうようにします。状態 q₁ と q₂ から出る遷移も同じようにします。すると、次のオートマトンが得られます。

このオートマトンが前のオートマトンと同じ言語を受理し、しかも状態が少ないことは明らかです。

状態の等価性

オートマトン A = ⟨Q, Σ, δ, q₀, F⟩ を考えます。状態 q ∈ Q の言語を L(q) で表し、次のように定義します。

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

つまり、オートマトン A の初期状態を q₀ から q に変えて、このオートマトンが受理する言語を求めます。言いかえると、言語 L(q) は、語 w のうち、オートマトン A で状態 q から w を読むと受理状態にたどり着くものすべての集合です。前のオートマトンにもどると、L(q₁) = {1} です。

異なる2つの状態 q₁ と q₂ が等価であるとは、次が成り立つことです。

$L (q_{1}) = L (q_{2})$

これはどういう意味でしょうか。状態 q₁, q₂ が等価なら、どちらをオートマトンの初期状態にしても、同じ言語を受理します。言いかえると、オートマトンが様相 ⟨q₁, w⟩ と ⟨q₂, w⟩ のどちらに入っても、両方とも受理するか、両方とも受理しないかのどちらかです。

前のオートマトンにもどると、状態 q₁ と q₂ は等価です。状態 q₁ にいるとき、入力語を受理できるのは、語のまだ読んでいない部分が1である場合だけだからです。状態 q₂ にいるときも同じです。

このように、オートマトンの最小化では、等価な状態を見つけ、上の例と同じようにそれらを1つの新しい状態にまとめます。

等価な状態の見つけ方

明らかに等価でないのは、どんな状態でしょうか。受理状態と非受理状態は、明らかに等価ではありません。受理状態の言語と非受理状態の言語は異なるからです。受理状態は必ず語 ε を受理しますが、非受理状態は受理しません。手順は、さっそく例で見てみましょう。次のオートマトンを考えます。

まず、状態の集合を2つつくります。

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

次に遷移表をつくり、グループ S₁ と S₂ の情報も残しておきます。

$\begin{array}{ccccc} グループ & 状態 & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

続いて、表を書きかえます。ある記号でどの状態に移るかを表に直接書くかわりに、移った先のグループだけを書いておきます。例えば、状態 q₃ から0で状態 q₅ に移り、この状態はグループ S₂ に属します。そこで、表には q₅ のかわりに S₂ と書きます。

$\begin{array}{ccccc} グループ & 状態 & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

ここで、2つのグループをさらに分けます。どの記号についても同じグループに移る状態どうしを、同じグループに入れます。例えば、状態 q₃ と q₆ は同じグループになりません。0についても1についても、同じグループに移らないからです。一方、状態 q₁ と q₂ は同じグループになります。どちらの状態も0の遷移をもたず、1ではどちらもグループ S₁ に移るからです。こうして、新しいグループができます。

$\begin{array}{ccccc} グループ & 状態 & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

どのグループの中でも、遷移は同じです。新しくできたグループに名前をつけ、それぞれの状態がこの新しいグループのどれに移るかを改めて調べます。

$\begin{array}{ccccc} グループ & 状態 & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

ここで、グループをさらに分けようとします。しかし、もうこれ以上は分けられず、同じグループが得られるだけです。状態 q₁ と q₂ はグループの単位で見ると同じ遷移をもちますが、すでに同じグループに入っていて、グループ S₄ にはほかの状態がないからです。これで、等価な状態を見つけるアルゴリズムは終わりです。あとは各グループから状態を1つずつ選び、ほかの状態を削除して、削除した状態に向かっていた遷移をすべて選んだ状態に向けるだけです。

例えば、新しいオートマトンの状態を q₃, q₆, q₀, q₁, q₄ とし、状態 q₂ と q₅ を取り除くことにします。すると、q₂ に向かっていた遷移はすべて q₁ に向かい、q₅ に向かっていた遷移はすべて q₄ に向かうようになります。

オートマトンの最小化の手順

到達不能状態を取り除きます。
冗長な状態を取り除きます。
等価な状態を1つにまとめます。

参考文献

章: 到達不能状態, 冗長な状態, オートマトンの最小化

« 前へ: 冗長な状態

次へ: 正規言語の閉包性 »