Brzozowskiのアルゴリズム - なぜDFAを2回反転すると最小化できるのか

概要

決定性有限状態オートマトン(DFA)は最小DFA(状態数が最小で等価なもの)を求めることで、一意になることが知られています。
この最小化(minimization)のアルゴリズムとして、HopcroftのアルゴリズムやMooreのアルゴリズムなどがありますが、その1つに次のようなBrzozowskiのアルゴリズムと呼ばれるものがあります。

Brzozowskiのアルゴリズム

DFA $M$について、$\mathrm{det}(\mathrm{rev}(\mathrm{det}(\mathrm{rev}(M))))$とすることで$M$の最小DFAとなる。
ここで、$\mathrm{rev}(M)$はDFA $M$の言語を反転させたものを受理するNFAを返す関数で、$\mathrm{det}(N)$はNFA $N$をサブセット構成法で決定化したDFAを返す関数とする。

つまり、DFAを決定化を挟んで2回反転させると最小DFAになる、ということです。

この一見すると不思議なアルゴリズムはWikipediaの「DFA minimization (英語)」のページや「正規表現技術入門」で紹介されていることから、それなりに知られているようですが、一方、このアルゴリズムでなぜ最小化できるかの説明はあまりありません(というか日本語で見たことがないです)。

ここでは、Brzozowskiのアルゴリズムの正当性を証明したいと思います。

準備

ここで定義する言葉は一般的なものなので、多くは読み飛ばしても構いません。
ですが、reachable・observableという概念はあまり一般的ではないので、確認するようにしてください。

有限の集合$A$について、$A$の部分集合全体からなる集合を$2^A$、$A$の元を並べた列(文字列)全体からなる集合を$A^\ast$で表すことにします。
また、空集合を$\varnothing$、空列を$\varepsilon$で表すことにします。

アルファベット$\Sigma$上の文字列$w \in \Sigma^\ast$について、文字を逆順に並べたものを$w$の反転とよび$w^{R}$で表します。
また、文字列の集合$L$の各元を反転させたものも$L^{R}$と表すことにします。

DFA、NFA、最小DFA、DFAの反転

DFA、NFAとそれらの言語について定義したあと、最小DFAがどのようなものか確認します。

非決定性有限状態オートマトン(NFA) $M$とは5つ組$(Q, \Sigma, \delta, I, F)$のことで、それぞれ次のような意味とします。

• $Q$は有限の状態集合
• $\Sigma$は有限の集合でアルファベット
• $\delta : Q \times \Sigma \to 2^Q$は遷移関数
• $I \subseteq Q$は初期状態
• $F \subseteq Q$は受理状態の集合

さらに$\delta$を$2^Q \times \Sigma \to 2^Q$に$\delta(S, \sigma) = \bigcup_{q \in S} \delta(q, a)$として自然に拡張できます。
また、$\delta^\ast : 2^Q \times \Sigma^\ast \to 2^Q$を$\delta^\ast(S, \varepsilon) = S,\ \delta^\ast(S, \sigma w) = \delta^\ast(\delta(S, \sigma), w)$と定義します。

NFA $M$が「文字列$w \in \Sigma^\ast$を受理する」とは$\delta^\ast(I, w) \cap F \ne \varnothing$であることとします。
NFA $M$の受理する文字列全体からなる集合を「$M$の言語」と呼び$L(M)$で表すことにします。

受理する言語の等しい2つのNFAを等価であると呼びます。

次に、NFA $M$の遷移関数のすべての遷移先と初期状態がただ1つの状態からなる集合であるとき、$M$を決定性有限状態オートマトン (DFA)とします。
また、初期状態のただ1つの状態を$i$で表し、遷移関数をただ1つの遷移先へ$\delta : Q \times \Sigma \to Q$のように拡張できます。
DFA $M$についてもNFAと同様に文字列に拡張された遷移関数$\delta^\ast : Q \times \Sigma^\ast \to Q$や受理する文字列、言語$L(M)$、等価性が定義されます。

DFA $M$の互いに異なる2つの状態$q_1, q_2 \in Q$について、次の式を満たすとき「2つの状態は区別できない」といいます。

$$
\forall w \in \Sigma^\ast. \delta^\ast(q_1, w) \in F \iff \delta^\ast(q_2, w) \in F
$$

そして、このような区別できない状態の組の存在しないDFAを最小であるといい、あるDFA $M$と受理する言語の等しい最小であるDFAを「$L(M)$を受理する最小DFA」とします。

DFA $M = (Q, \Sigma, \delta, i, F)$について、「$M$を反転させたNFA」を$\mathrm{rev}(M) = (Q, \Sigma, \delta^{R}, F, \{i\})$とします。
ここで$\delta^{R}(q, a) = \{ p \in Q | \delta(p, a) = p \}$です。
$\delta^R$はDFAを図にしたときの遷移を表す矢印をちょうど逆向きにしたようなイメージで、そのため遷移先が1つに定まるとは限らず、反転させた結果がNFAとなることに注意してください。
この$\mathrm{rev}(M)$の受理する言語$L(\mathrm{rev}(M))$は、もとのNFAの言語を反転させたもの$L(M)^R$になります。

reachable、observable、NFAの決定化

DFAについてrechable、observableという概念を定義して、この観点からDFAが最小となる条件を見直します。
この概念はあまり一般的ではありませんが、Brzozowskiのアルゴリズムの正当性を確認する上で非常に重要となります。

DFA $M$について、「状態$q$がreachable (到達可能)である」とは、ある文字列$w \in \Sigma^\ast$が存在して$\delta^\ast(i, w) = q$となることとします。
つまり、初期状態から何らかの文字列で状態$q$へと遷移できる、ということです。
すべての状態がreachableであるとき、そのDFA $M$をreachableである、ということにします。

続けて、DFA $M$について「状態$q$がobservable (観測可能)である」とは、ある文字列$w \in \Sigma^\ast$が存在して$\delta^\ast(q, w) \in F$となることとします。
つまり、その状態から何らかの文字列で受理状態へと遷移できる、ということです。

DFA $M$の状態$q \in Q$について、初期状態$q_0$から$q$へと遷移する文字列全体からなる集合を$r_M(q) = \{ w \in \Sigma^\ast | \delta^\ast(q_0, w) = q \}$とし、$q$から受理状態へと遷移する文字列全体からなる集合を$o_M(q) = \{ w \in \Sigma^\ast | \delta^\ast(q, w) \in F \}$とします。

このとき、$r_M(q)$の性質として次のことが言えます。

定理 reachableなDFA $M$の任意の相異なる2つの状態$q_1, q_2 \in Q$について、$r_M(q_1)$と$r_M(q_2)$は異なる。

証明 DFAの遷移は決定的なので明らか。$\blacksquare$

もしDFAがreachableでなけば、$r_M(q)$が空集合となるような状態が複数存在する可能性があり、上の定理が成り立たない場合があることは地味ですが重要なところだと思います。

また、$o_M(q)$を使ってDFAの最小性の定義を次のように言い換えられます。

定義 DFA $M$の任意の相異なる2つの状態$q_1, q_2 \in Q$について$o_M(q_1)$と$o_M(q_2)$が異なるとき、$M$を最小である、という。

実際、2つの状態$q_1, q_2$が区別できないことの定義が$o_M(q_1) = o_M(q_2)$と表せることからも上の定義が妥当であることは分かると思います。

最後に、NFA $M$の決定化について確認します。
NFA $M = (Q, \Sigma, \delta, I, F)$について、DFA $(2^Q, \Sigma, \delta, I, \{ S \in 2^Q | \exists q \in F. q \in S \})$とすると、このDFAは$M$と等価になります。
このようにしてあるNFAと等価なDFAを得ることをサブセット構成法と呼びます。
ここでは、NFAを決定化した上で、さらにreachableでない状態を除いたものを$\mathrm{det}(M)$で表すことにします。

初期状態から幅優先探索のようにしてサブセット構成法を実装すれば、基本的にはreachableになるので、実装の際にはそこまで気にする必要はありません。

本題

実はBrzozowskiのアルゴリズムは次の定理の系として得られます。

定理 reachableなDFA $M$について、DFA $\mathrm{det}(\mathrm{rev}(M))$は$L(M)^R$を受理する最小DFAとなる。

Brzozowskiのアルゴリズムでは$\mathrm{det}(\mathrm{rev}(M))$を2回を行います。
最初のこの処理で$M$を反転させた言語を受理するreachableなDFAとなり、このことで2回目では上の定理が適用され、最終的に$M$を2回反転させた(つまり元の言語と等しい)言語を受理する最小DFAとなっている、というわけです。

それでは、この定理を証明しましょう。

証明

DFA $M = (Q, \Sigma, \delta, i, F)$とおきます。
また、$N = \mathrm{det}(\mathrm{rev}(M))$とします。
反転してから決定化した際に到達可能な状態の族を$P \subseteq 2^Q$とすると、$N = (P, \Sigma, \delta^R, F, \{ S \in P | i \in S \})$となります。

$N$が言語$L(M)^R$を受理するのは自明なので、最小DFAであることを示すには、異なる2つの状態$S_1, S_2 \in P$について$o_N(S_1)$と$o_N(S_2)$が異なることを示す必要があります。

$o_N(S)$は$S$から$N$の受理状態へと遷移する文字列全体からなる集合のことでした。
ここで、$N$の受理状態とは元のDFA $M$の初期状態$i$を含む状態の集合だということに注意すると、$o_N(S)$は次のように$r_M(q)$を使って表せます。

$$
o_N(S) = r_M(q_1)^R \cup r_M(q_2)^R \cup \cdots \cup r_M(q_k)^R
\ \ \ (S = \{ q_1, q_2, \cdots, q_k \})
$$

DFA $M$はreachableなので各$r_M(q_1), r_M(q_2), \cdots, r_M(q_k)$はそれぞれ異なります。
ということは、$o_N(S_1)$と$o_N(S_2)$が等しいのは$S_1 = S_2$のときかつそのときに限ります。
よって、相異なる$S_1, S_2$では$o_N(S_1)$と$o_N(S_2)$が異なることも分かり、$N$が$L(M)^R$を受理する最小DFAであることが示されました。
$\blacksquare$

無事、定理を示すことができました。
これでBrzozowskiのアルゴリズムの正当性も確認できたかと思います。

あとがき

本題の証明よりも準備の方が長くなってしまいました。
reachableやobservableの定義を本題に持ってきてもよかったのですが、そうすると$\mathrm{det}(M)$の定義が前後してしまうのでこのようになっています。

この証明の本質は、反転すると$r_M(q)$が一意であるという性質も含めて、reachableとobservableが入れ替わる、というところにあると思います。
こうした対応はreachableとobservableの双対性にあるそうですが、自分はそこまで分かっているわけではないのでこれ以上の言及は避けておきます。

それでは、ここまで読んでいただきありがとうございました。

参考文献

1. Brzozowski, Janusz A. "Canonical regular expressions and minimal state graphs for definite events." Mathematical theory of Automata 12.6 (1962): 529-561.
2. Bonchi, Filippo, et al. "Brzozowski’s algorithm (co) algebraically." Logic and Program Semantics. Springer, Berlin, Heidelberg, 2012. 12-23.
3. García Gómez, Pedro, Damián López Rodríguez, and Manuel Vázquez-De-Parga Andrade. "DFA minimization: from Brzozowski to Hopcroft." (2013).

1はBrzozowskiによる原論文ですが、かなり古い論文であり、またそれなりにページ数もあるので読むのは大変だと思います。

2はreachablityとobservabilityの双対性に着目してBrzozowskiのアルゴリズムの証明を与えるものです。
この記事はこの論文の内容を大変参考にしているのですが、この論文は全体を通して普遍代数の言葉で記述されているため難しく感じます。

3はBrzozowskiのアルゴリズムを通してDFAの最小化アルゴリズムについて考察し、Hopcroftのアルゴリズムの状態を分割するような処理がBrzozowskiのアルゴリズムとどのように関係するのかを説明したものです。
この記事とは直接の関係はありませんが、各種の定義などで参考にしたので上げておきます。