提案手法を用いた拡張 Brzozowski アルゴリズムと Hopcroft によ るアルゴリズムを用いた DFA 最小化の実行時間の比較

提案実装手法1^′を用いた拡張BrzozowskiアルゴリズムとHopcroftによるアルゴリズム を用いたDFA最小化の実行時間を調べた．アルゴリズムの違いによるDFA最小化の実行 時間の比較結果を図5.5，5.6に示す．ただし，図5.5は，入力のDFAM = (Q,Σ, δ, I, F) のアルファベットサイズを固定して，状態数|Q|を変化させた場合の，図5.6は，入力の DFAの状態数を固定して，アルファベットサイズを変化させた場合の，Mと等価で状態

𝑎 2 1

0

7

3

𝑎 6 𝑎

5 𝑎

4 𝑎 𝑎

𝑎 𝑎

𝑏 𝑏

𝑏 𝑏 𝑏

𝑏

𝑏 𝑏 𝑏

{2,3}

{0,1} 𝑎

{6,7}

𝑎

𝑏 𝑏

{4,5}

𝑎 𝑎

入力 𝑏

Hopcroftによる アルゴリズム

の状態集合

出力 DFA構築

図 5.4: Hopcroftによるアルゴリズムを用いたDFA最小化の例．

数最小のDFAを求める実行時間をそれぞれ示している．この出力の実行時間は，FAdo を用いて，各入力条件について，ランダムに生成した200個のDFA M に対する，最小 のDFAを求める時間の平均である．各図においてProposed methodとあるのは，アト ミック化に提案実装手法1^′（Algorithm 6）を用いた拡張Brzozowskiアルゴリズムの結果 である．なお，反転にはFAdoのreversal関数を用いて，決定性化には，Hopcroftによる アルゴリズムに合わせて，右言語が空な状態も求めるものを実装して用いた．Hopcroft とあるのは，状態集合の導出に，[3]の疑似コードをもとに実装したHopcroftによるアル ゴリズムを用いた場合の結果である．その実装は，V´azquezらのアルゴリズムの実装と 同様に，疑似コード中の集合はPythonのsetを，組はtupleをそれぞれ素朴に用いたも のである．また，この結果には，状態集合の導出部分に加えて，DFAの構築部分の実行 時間も含まれる．すなわち，純粋な元論文 [4]のアルゴリズムの実行時間ではない．

図5.5，5.6より，本実験の条件と実装においては，状態数が大きく，アルファベット サイズが小さいときに，提案手法を用いた拡張Brzozowskiアルゴリズムの実行時間の方 が短いという結果となった．この結果について，V´azquezらのアルゴリズムでは，出力 のNFAの状態数や，出力の状態のサイズの総和が大きくなるときに，計算量も大きくな ると考えられる．しかし，図4.2などからわかるように，出力の平均状態数は必ずしも 大きくなく，図3.11などにあるように，出力の状態数や状態のサイズの総和を大きくす

0 25 50 75 100 125 150 175 200

|Q|

0.00 0.01 0.02 0.03 0.04

time[sec]

Proposed method Hopcroft

図 5.5: 提案実装手法1^′を用いた拡張BrzozowskiアルゴリズムとHopcroftによるアルゴ リズムを用いたDFA最小化の実行時間の比較（|Σ|= 2）．

0 2 4 6 8 10 12 14 16

alphabet size 0.00

0.05 0.10 0.15 0.20

time[sec]

Proposed method Hopcroft

図 5.6: 提案実装手法1^′を用いた拡張BrzozowskiアルゴリズムとHopcroftによるアルゴ リズムを用いたDFA最小化の実行時間の比較（|Q|= 140）．

るには，状態や文字の選択順も重要である．また，図4.2，4.3を比較することで，アル ファベットサイズが大きいときに，出力の平均状態数も大きくなることがわかる．これ らが，結果に影響したものと考えられる．

第 6 ^章

結論

 本論文では，DFAの状態数の最小化アルゴリズムの一種である，Brzozowskiアルゴリ ズムと拡張Brzozowskiアルゴリズムについて，その計算量に影響を及ぼす両アルゴリズ ムの2回目の操作，特に拡張Brzozowskiアルゴリズムのアトミック化に着目した．

まず，V´azquezらが提案したアトミック化に対し，その入力が任意のNFAの場合と，

DFAを反転したものの場合に分けて，入力のNFAのアルファベットサイズ別に，その出 力のNFAの状態数の最大値と最小値を示すとともに，出力の状態数が最大や最小となる 入力例を示した．

続いて，両方の最小化アルゴリズムの2回目の操作の後のNFAの状態数を，入力の DFAのアルファベットサイズを2として実験的に比較し，V´azquezらのアルゴリズムを 用いた拡張版の方が，最悪の場合だけでなく，平均でも状態数が大幅に少なくなるとい う結果となった．

さらに，V´azquezらのアルゴリズムで任意性のある，状態と文字の選択順を工夫するこ

とで，出力のNFAの平均状態数を削減できることや，V´azquezらのアルゴリズムの実装 を工夫することで，素朴な実装と比較して，V´azquezらのアルゴリズム自身及びV´azquez らのアルゴリズムを用いた拡張Brzozowskiアルゴリズムのそれぞれの実行時間を大幅に 削減できることを述べた．

今後の課題としては，提案実装手法の計算量の解析，V´azquezらのアルゴリズムで出 力の状態数や実行時間を削減するより良い手法の考案，及びV´azquezらのアルゴリズム に代わるアトミック化の考案などがあげられる．

参考文献

[1] 丸岡章. 計算理論とオートマトン言語理論―コンピュータの原理を明かす―. サイエ ンス社, 2005.

[2] 広瀬貞樹. オートマトン・形式言語理論. コロナ社, 2014.

[3] Jean Berstel, Luc Boasson, Olivier Carton, and Isabelle Fagnot. Minimization of automata. CoRR, Vol. abs/1010.5318, pp. 1–37, 2010.

[4] John E. Hopcroft. An nlogn algorithm for minimizing states in a finite automaton.

Technical report, Stanford, CA, USA, 1971.

[5] Janusz Brzozowski. Canonical regular expressions and minimal state graphs for defi-nite events. Mathematical theory of Automata, Vol. 12, No. 6, pp. 529–561, 1962.

[6] Pedro Garc´ıa, Dami´an L´opez, and Manuel V´azquez de Parga. DFA minimization:

Double reversal versus split minimization algorithms. Theoretical Computer Science, Vol. 583, pp. 78–85, 2015.

[7] Janusz Brzozowski and Hellis Tamm. Theory of Atomata. In Giancarlo Mauri and Alberto Leporati, editors, Developments in Language Theory, pp. 105–116, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.

[8] Manuel V´azquez de Parga, Pedro Garc´ıa, and Dami´an L´opez. A polynomial dou-ble reversal minimization algorithm for deterministic finite automata. Theoretical Computer Science, Vol. 487, pp. 17–22, 2013.

[9] Fado 1.3.5.1. https://pypi.org/project/FAdo/.