DFAの状態数最小化アルゴリズム

この記事はIS18er Advent Calendarの20日目の記事として書かれました。 別に大した話ではないのですが,アドベントカレンダーを埋めるために無理やり引っ張り出してきたネタです。

形式言語理論の授業で扱ったDFA(決定性有限オートマトン)の状態数最小化アルゴリズムを,具体的なDFAについて実装して実験してみたというお話です。 最小化アルゴリズムについては第5週の課題で扱っていて,その時にも実装をしてレポートとして出していたのですが,今週(第9週)の宿題もまた最小化に関連していて面白いなあと思ったので再び実装してみました。

状態数最小化アルゴリズムとは

ある正規言語を受理するDFAは幾通りも存在することがありえますが,その中で状態数が最小になるものを求めるアルゴリズムです。 このアルゴリズムの結果として求められるDFAは互いに同型(isomorphic)になります。

この性質のおかげで,状態数最小化によりオートマトンが実装しやすくなるだけでなく,2つの正規言語が同一のものであるかどうかをそれを受理する状態数最小のDFAが同型であるかどうかという問題に帰着させることができます。

基本的な流れ

最小化アルゴリズムにおいては,元のDFAにおいて異なっていた2つの状態が区別不可能であるならば,それらを統合する,ということを繰り返していきます。 ここで,二項関係「状態 q, q' \in Q が区別不可能である」は同値関係で,以下のように定義されます。

任意の語  w \in \Sigma^{*} に対して,  \delta^{*} (q, w) \in F \Leftrightarrow \delta^{*} (q', w) \in F

蓮尾先生の言葉を借りれば「canonical automatonにおいてのcoloringが同じ」ということですね。 そして,区別不可能な状態を求めるアルゴリズムの例として教科書で紹介されていたのが以下のようなものです。

f:id:momohatt:20171220145524p:plain

(図は教科書に従って作成)

これはつまり, Fの要素と Q-Fの要素だけが互いに区別可能で,それ以外の組み合わせは区別不可能であるという初期状態から出発して,区別不可能なペアの集合を1つずつ減らしていく(区別可能であるとする)という方法になります。

これを実装してみます。

今回対象とした問題について

今回の問題設定を説明します。 アルファベットを {0, 1}とした記号列のうち,10110を部分語として含むような言語を受理するオートマトンを最小化する問題を考えました。 最小化する前のDFAは以下のようにするとします。

  •  Q = \{00000, 00001, 00010, \cdots 11111 \}

  •  \Sigma = \{0, 1\}

  •  F = \{10110\}

  •  q_0 = 00000

  • 
{\delta =
\left\{
  \begin{array}{ll}
    (10110, 0, 10110), (10110, 1, 10110) \quad (現在の状態が10110の場合) \\
    (a_1 a_2 a_3 a_4 a_5, 0, a_2 a_3 a_4 a_5 0), (a_1 a_2 a_3 a_4 a_5, 1, a_2 a_3 a_4 a_5 1) \quad (otherwise) \\
  \end{array}
\right.}

つまり,「現在の位置から4文字前の文字」から「現在の位置の文字」までの連続5文字に対応するような状態を持つようにし,初期状態は00000であるとしています。また,一度10110に到達した後は移動しないという設定です。

最小化した結果は以下のようになります。割と最小化した結果が最初に出てもおかしくないくらいには単純な気がしますが気にしないでいきましょう

f:id:momohatt:20171220154925p:plain

実装では,縮小前の各状態を2進数と見なし,それらを10進数で置き換えています。つまり例えば状態10110は22などと表現しています。

結果が以下のようになります。

set([22])
set([0, 4, 8, 12, 16, 20, 24, 28])
set([1, 3, 7, 9, 15, 17, 19, 23, 25, 31])
set([2, 6, 10, 14, 18, 26, 30])
set([29, 21, 5, 13])
set([27, 11])

区別可能な状態が6つあることがわかりました。

もう1つのアルゴリズム

その後の形式言語理論の宿題で,別の最小化アルゴリズムを証明する問題が出ました。以下のようなものです。

f:id:momohatt:20171220151141p:plain

ここで  \Phi というのは

 (q, q') \in \Phi (R) \Leftrightarrow \left( q \in F \Leftrightarrow q' \in F かつ \forall a \in \Sigma \quad (\delta(q, a), \delta(q', a)) \in R\right)

のように定義されるのですが,ここで R \supseteq \Phi(R) \supseteq \Phi(\Phi(R)) \cdotsであるということと, \cap_{n \in \mathbb{N}} \Phi^{n}(R)が区別不可能な状態のペアの集合になることが示せるので,これを用いても状態数最小化を実現することができます。以下のようになります。

得られる結果は前のものと同じです(順番は異なります)。ただ,上のアルゴリズムでは,UnmarkedListから1つのペアを除くたびに探索を最初に戻ってやり直しているのに対し,こちらのアルゴリズムでは一度の探索でUnmarkedListから一度に幾つかのペアをまとめて除いているので,無駄な探索が少なく,より高速に求めることができるようになっています。

まとめ

よく考えれば上の2つのアルゴリズムは本質的には同じことをやっているとわかります。先生もおそらく,教科書に掲載しているアルゴリズムの解説のためにあの問題を出題したのかなと思いました。解説を聞くのが楽しみです。