著者
若張 直紀
学位授与機関
Tohoku University
Brzozowski
系の
DFA
最小化アルゴリズムの
解析に関する研究
東北大学 大学院情報科学研究科
システム情報科学専攻 篠原・吉仲研究室
博士課程前期
2
年の課程
若張 直紀
2020
年
2
月
21
日
目次
第 1 章 序論 1 1.1 はじめに . . . . 1 1.2 構成 . . . . 3 第 2 章 準備 4 2.1 言語及び有限オートマトン . . . . 4 2.2 多項式時間アトミック化アルゴリズム . . . . 8 2.3 DFA の Brzozowski 系状態数最小化アルゴリズム . . . . 12 第 3 章 V´azquez らのアルゴリズムの出力の状態数の解析 16 3.1 任意の NFA を入力とする場合の出力の最大状態数 . . . . 16 3.1.1 |Σ| = 1 のとき . . . . 18 3.1.2 |Σ| ≥ 2 のとき . . . . 20 3.2 到達可能な DFA を反転したものを入力とする場合の出力の最大状態数 . 21 3.2.1 |Σ| = 1 のとき . . . . 23 3.2.2 |Σ| ≥ 2 のとき . . . . 25 3.3 V´azquez らのアルゴリズムの出力の状態数 . . . . 27 第 4 章 V´azquez らのアルゴリズムの出力の平均状態数の削減 31 4.1 出力の平均状態数を削減するため検討 . . . . 31 4.2 実験 4.2：Brzozowski 系アルゴリズムの中間状態数の比較 . . . . 33 4.3 実験 4.3：状態の選択順による出力の状態数の変化 . . . . 33 4.4 実験 4.4：文字の選択順による出力の状態数の変化 . . . . 36 4.5 実験 4.5：状態と文字の選択順による出力の状態数の変化 . . . . 36 4.6 より有効な選択順の検討 . . . . 384.6.1 状態の選択順 . . . . 38 4.6.2 文字の選択順 . . . . 40 第 5 章 V´azquez らのアルゴリズムの高速な実装手法の考案 43 5.1 提案アルゴリズム . . . . 43 5.2 実験 5.2：実装手法の違いによる V´azquez らのアルゴリズムの実行時間の 違い . . . . 48 5.3 実験 5.3：アトミック化の実装手法の違いによる拡張 Brzozowski アルゴリ ズムの実行時間の違い . . . . 50 5.4 Brzozowski 系アルゴリズムと Hopcroft によるアルゴリズム . . . . 51 5.5 提案手法を用いた拡張 Brzozowski アルゴリズムと Hopcroft によるアルゴ リズムを用いた DFA 最小化の実行時間の比較 . . . . 51 第 6 章 結論 55 参考文献 56
第
1
章
序論
1.1
はじめに
有限オートマトンは，メモリが有限なコンピュータの動作をモデル化したものの一つ である [1]．具体的には，文字列 w を入力とし，その文字列 w を受理するか否かを出力す るものである．ある有限オートマトンで受理される文字列の集合を，その有限オートマ トンで受理される言語と呼ぶ．有限オートマトンには，決定性有限オートマトン（DFA） や非決定性有限オートマトン（NFA）等があり，ある言語を受理する有限オートマトン は，一般に複数存在する．これは，DFA や NFA に限ったとしても同様であり，状態数や 状態遷移が互いに異なる DFA（または NFA）が，同じ言語を受理することがある．そこ で，ある言語を受理する有限オートマトンの中で最もシンプルなもの（ここでは最も状 態数の少ないもの）をいかに求めるかという関心が生じる． 有限オートマトンの状態数の最小化によってできることには，主に以下の二つがある． 一つ目は，2 つの有限オートマトンに対して，それらが同じ言語を受理するか否かを判定 することである．ある言語を受理する DFA のなかで，状態数最小なものはただ１つであ るから，与えられた有限オートマトンと等価な状態数最小 DFA をそれぞれ求めて，その 状態数最小 DFA 同士を比較すればよい [2]． 二つ目は，効率的な実装が可能になるということである．前述のように，有限オート マトンは，コンピュータの動作をモデル化したものであった．よって，実システムの設 計等で，システムの要件を満たす有限オートマトンを，たとえそれが冗長なものであっ たとしても構築できれば，その有限オートマトンと等価で状態数最小な有限オートマトンを求めることができる．そして，この状態数最小の有限オートマトンをもとにするこ とで，より効率的な実装が可能になる．状態数の最小化は，論理設計，コンパイラ，文 字列処理，及び画像解析等で利用実績がある [2, 3]． DFA の最小化の基本的な考え方は，同じ働きをするとみなせる状態を一つにまとめる ことである．これを実現する直感的な方法として，最小化したい DFA の状態を，はじめ に最終状態のグループと非最終状態のグループに分割し，さらに各グループの状態の遷 移先が同じグループになるか否かで分割していくことを繰り返すものがある．こうした 考えによる Hopcroft によるアルゴリズム [4] の実行時間は，n を入力の DFA の状態数と して，O(n log n) である．一方，NFA の初期状態と最終状態を交換し，全ての状態遷移を 逆にする操作を反転とよぶが，反転と決定性化を 2 回繰り返すことで状態数最小の DFA を得るという，Brzozowski によるアルゴリズム [5] が存在する．この Brzozowski による アルゴリズムは，最悪時計算量は指数時間であるが，入力によっては非常に効率的なこ と，（DFA だけでなく）NFA も入力とできること，及び処理手順や実装が分かりやすいと いった，優れた面もある [3]．なお，これらの，分割を繰り返す方法と，2 回反転（と決 定性化）を行う方法は，相互の関係性が指摘されている [6]．
Brzozowski によるアルゴリズムは，入力の DFA（または NFA）を反転して，決定性化 （DFA 化）して，さらに反転して，決定性化するものであるが，1 回目の決定性化の後の 状態数が，入力の DFA の状態数を n とすると，最大で 2nになるのが問題であった．し かし，この 1 回目の決定性化を，NFA のクラスの一つであるアトミックな NFA を得る 操作に拡張しても，DFA を最小化できることが示された [7]．V´azquez ら [8] は，状態数 n の NFA を入力とし，最大でも状態数が 2n− 1 であるアトミックな NFA を求めるアル ゴリズムを示し，これら Brzozowski アルゴリズムの拡張とアトミック化アルゴリズムに よって，多項式時間の DFA の最小化アルゴリズムが実現された． そこで本論文では，DFA の状態数の最小化アルゴリズムの一種である，Brzozowski に よるアルゴリズムとその拡張版アルゴリズムについて，その計算量に影響を及ぼす両ア ルゴリズムの 2 回目の操作，特に拡張版アルゴリズムのアトミック化に着目する．そし て，V´azquez らの解析では言及されていなかった，DFA を反転したものをアトミック化 した場合の出力の状態数，及び出力の状態数が最大となる入力例等について述べる．ま
た，両方の最小化アルゴリズムの 2 回目の操作の後の NFA の状態数を，実験的に比較す る．さらに，V´azquez らのアルゴリズムで任意性のある部分の工夫による，出力の平均 状態数の削減や，実装手法の工夫による高速化についても述べる．
1.2
構成
本論文の構成を以下に示す．第 2 章では，本論文で用いる用語を定義したうえで，V´azquez らのアルゴリズム，Brzozowski によるアルゴリズム，及びその拡張版アルゴリズムを説 明する．第 3 章では，V´azquez らのアルゴリズムについて，その出力の NFA の最大・最 小状態数，及び出力の状態数が最大・最小となる入力例について述べる．第 4 章では，両 方の最小化アルゴリズムの途中の NFA の状態数を，実験的に比較した結果を示すととも に，V´azquez らのアルゴリズムで任意性のある，状態と文字の選択順の工夫による，出 力の平均状態数の削減について述べる．第 5 章では，V´azquez らのアルゴリズムの高速 な実装手法について述べる．最後に，第 6 章で本論文をまとめる．第
2
章
準備
2.1
言語及び有限オートマトン
Σ を有限のアルファベットとする．Σ の元である記号を有限個並べたものを，文字列と 呼ぶ．長さが 0 の文字列を空文字列と呼び，ϵ で表す．文字列 w の長さを，|w| と表す．Σ 上のすべての文字列からなる集合を，Σ∗と表す．Σ∗の任意の部分集合を，Σ 上の言語と 呼ぶ． Σ 上の言語 L, K について，補集合 L = Σ∗ \ L = {w ∈ Σ∗ | w /∈ L}，和集合 K ∪ L = {w ∈ Σ∗ | w ∈ K or w ∈ L}，積集合 K ∩ L = {w ∈ Σ∗ | w ∈ K and w ∈ L}，連結 KL ={w ∈ Σ∗ | w = uv, u ∈ K, v ∈ L} をそれぞれ用いる．また，2Sを，集合 S の冪集 合とする．非決定性有限オートマトン（Nondeterministic Finite Automaton, NFA）は，5 項組
M = (Q, Σ, δ, I, F ) であり，Q は状態の有限で非空な集合，Σ は有限で非空なアルファ ベット，δ : Q× Σ → 2Qは遷移関数，I ⊆ Q は初期状態の集合，及び F ⊆ Q は最終状 態の集合である． ここで，遷移関数 δ は，δ′ : Q× Σ∗ → 2Q及び δ′′: 2Q× Σ∗ → 2Qへ拡張して用いる場合 もある．ただし，δ′ : Q×Σ∗ → 2Qは，δ : Q×Σ → 2Qに対して，状態 q∈ Q，文字 a ∈ Σ， 文字列 w∈ Σ∗を用いて，δ′(q, ϵ) ={q} かつ δ′(q, aw) = δ′(δ(q, a), w) と拡張したものであ る．また，δ′′ : 2Q× Σ∗ → 2Qは，δ′ : Q× Σ∗ → 2Qに対して，状態 q∈ Q，状態の部分集 合 P ⊆ Q，文字列 w ∈ Σ∗を用いて，δ′′(∅, w) = ∅ かつ δ′′({q}∪P, w) = δ′(q, w)∪δ′′(P, w) と拡張したものである．今後，遷移関数 δ，δ′，及び δ′′の表記は区別せず，全てに対して
NFA
図 2.1: NFA M の一例． δ を用いる． NFA M によって受理される言語は，L(M ) ={w ∈ Σ∗ | δ(I, w) ∩ F ̸= ∅} である．2 つ の NFA が同じ言語を受理するとき，それらは等価であるという．NFA M の状態 q の左 言語は，LI,q(M ) ={w ∈ Σ∗ | q ∈ δ(I, w)} である．状態 q の右言語は，Lq,F(M ) ={w ∈ Σ∗ | δ(q, w) ∩ F ̸= ∅} である．状態 q の左言語が空である時，その状態 q は到達不可能と 呼ぶ．到達不可能な状態を持たないとき，その NFA は到達可能であるという． 例 1. 図 2.1 に示す NFA M = (Q, Σ, δ, I, F ) について，各状態の左言語は，LI,0(M ) ={ϵ}，LI,1(M ) ={a}，LI,2(M ) ={b}，及び LI,3(M ) ={ab, ba} である．
また，M の各状態の右言語は，L0,F(M ) ={a, ab, b, ba}，L1,F(M ) ={ϵ, b}，L2,F(M ) =
{ϵ, a}，及び L3,F(M ) ={ϵ} である．
決定性有限オートマトン（Deterministic Finite Auotmaton, DFA）は，5 項組 M =
(Q, Σ, δ,{q0}, F ) であり，Q，Σ，δ，及び F は NFA と同様であるが，δ の値域は単集合に 制限されたものであり，q0は初期状態である．すなわち，DFA は，初期状態集合が{q0}， 遷移関数の値域が集合 Q の単集合に制限された NFA である．到達不可能な状態を持た ず，互いに等価な状態を含まない DFA は，最小である． NFA M = (Q, Σ, δ, I, F ) について，M の初期状態と最終状態を交換し，全ての状態遷 移を逆にする操作を反転と呼ぶ．M を反転したもの Rev(M ) は，q ∈ δR(p, a) ⇐⇒ p ∈
δ(q, a) である NFA Rev(M ) = (Q, Σ, δR, F, I) である．すなわち，Rev(Rev(M )) = M が
2 0 1 2 0 1 反転 NFA NFA 図 2.2: 反転の例． 例 2. 図 2.2 に反転の例を示す．図 2.2 では，NFA M で初期状態である状態 0 が，NFA Rev(M ) では最終状態となっている．また，M で最終状態である状態 0, 2 が，Rev(M ) で は初期状態となっている．状態遷移については，例えば，M で状態 1 から 0 に文字 a に よる遷移があるが，Rev(M ) では状態 0 から 1 の向きとなっている． NFA M = (Q, Σ, δ, I, F ) について，F′ = {P ∈ 2Q | P ∩ F ̸= ∅}，δ′(P, a) = ∪ p∈Pδ(p, a) = δ(P, a) である M′ = (2 Q, Σ, δ′,{I}, F′) を考える．この M′ は，M と等 価な DFA であり，M′を到達可能にしたものを Det(M ) と表す．具体的には，Q′′ ={R ∈ 2Q | L {I},R(M′)̸= ∅}，R ∈ Q′′である R について δ′′(R, a) = δ′(R, a)，及び F′′ = F′∩ Q′′
に対して，Det(M ) = (Q′′, Σ, δ′′,{I}, F′′) である．Det(M ) を求めることを，決定性化と
呼ぶ．決定性化には，状態 I を出力の初期状態として，状態からの遷移先を繰り返し求 めていく，部分集合法を用いる． 例 3. 図 2.3 に決定性化の例を示す．まず，NFA M の初期状態 0, 2 をまとめた状態{0, 2} を，求める Det(M ) の初期状態とする．続いて，状態{0, 2} からの遷移先を調べる．文 字 a について，M における状態 0 からの遷移先は 0, 1，状態 2 からの遷移先は 2 である から，Det(M ) において，状態{0, 2} からの遷移先として {0, 1, 2} を追加する．また，文 字 b について，M における状態 0, 2 からの遷移先は 1, 2 であるから，Det(M ) において， 状態{0, 2} からの遷移先として {1, 2} を追加する．同様にして，新たに追加された状態 の遷移先を調べていくと，図 2.3 に示す Det(M ) が求まる． 文字列 w による言語 L の左商（または商) とは，言語 w−1L = {x ∈ Σ∗ | wx ∈ L} で ある．NFA M が受理する言語 L(M ) の左商集合は有限である．空でない言語 L′ が，L の左商集合{L1, L2, ..., Ln} に対して， eLi ∈ {Li, Li} を用いて L′ = fL1∩ fL2∩ ... ∩ fLnと 書け，かつ L′ ̸= L 1∩ L2∩ ... ∩ Lnであるとき，L′は L のアトムであるという．NFA M
決定性化 NFA DFA 2 0 1 {0,2} {0,1,2} {1,2} {0,1} {2} ∅ {1} {0} 図 2.3: 決定性化の例． について，その全ての状態の右言語が，L(M ) のアトムの和集合であるとき，M はアト ミックであるという．
例 4. アルファベット Σ = {a, b} 上の言語 L = {a, ab, b, ba} について，L0 = ϵ−1L =
{a, ab, b, ba}，L1 = a−1L ={ϵ, b}，L2 = b−1L ={ϵ, a}，及び L3 = (ab)−1L = (ba)−1L =
{ϵ} はそれぞれ，L の左商である．
また，L0∩ L1∩ L2∩ L3 ={a}，L0∩ L1∩ L2∩ L3 ={b}，L0∩ L1∩ L2∩ L3 ={ab, ba}， 及び L0∩ L1∩ L2∩ L3 ={ϵ} はそれぞれ，L のアトムである．
例 5. 図 2.1 に示す NFA M = (Q, Σ, δ, I, F ) について，M の各状態の右言語は，L0,F(M ) =
{a, ab, b, ba}，L1,F(M ) = {ϵ, b}，L2,F(M ) = {ϵ, a}，及び L3,F(M ) = {ϵ} である．ここ
で，L(M ) = {a, ab, b, ba} のアトムは，例 4 より，{a}，{b}，{ab, ba}，及び {ϵ} である
が，N の各状態の右言語は，L0,F(M ) = {a} ∪ {b} ∪ {ab, ba}，L1,F(M ) = {b} ∪ {ϵ}，
L2,F(M ) = {a} ∪ {ϵ}，及び L3,F(M ) ={ϵ} のように，それぞれ L(M) のアトムの和集合
で表せるため，M はアトミックである．
定義 1 で，NFA のレプリカを定義する．NFA M のレプリカは，M と等価な NFA の一 種である．
定義 1 (V´azquez, Garc´ıa, and L´opez [8]). NFA M = (Q, Σ, δ, I, F ) に対して，以下の条
件を満たす到達可能な NFA M′ = (Q′, Σ, δ′, I′, F′) を，M のレプリカと呼ぶ．
{1,2} ∅ {0,1,2,3} {1,2} {0,3} {1} {2} {0,2} {1,3} {0,1} {2,3} NFA NFA NFA NFA 図 2.4: NFA M とそのレプリカの一部 M1, M2, 及び M3． • I =∪P∈I′P ． • F′ ={P ∈ Q′ | P ∩ F ̸= ∅}． • ∀P ∈ Q′,∀a ∈ Σ, δ′(P, a) ={P 1, ..., Pk}．ただし，Pi ∈ Q′，δ(P, a) = ∪k i=1Pi． M のレプリカは，一般に複数存在する． 例 6. 図 2.4 にレプリカの例を示す．NFA M のレプリカとしては，例えば，M に部分集 合法を適用した M1 = Det(M ) がある．また，部分集合法ではある文字による遷移先状 態はただ一つであるが，2 つ以上の状態に分割遷移させた M2のようなものも，M のレプ リカである．さらに，初期状態を分割させた M3のようなものも，M のレプリカである． 集合 Q について，Q = ∪1≤i≤kPiを満たす，Q の互いに素で非空な部分集合 Piの集合 {P1, P2, ..., Pk} を，集合 Q の分割と呼ぶ．S | P = {P ∩S, P \S}\{∅} を，P の S による分 割と呼ぶ．また，集合 Q の２つの分割P, P′に対し，P∧P′ ={P ∩P′ | P ∈ P, P′ ∈ P′}\{∅} を，P と P′の粗分割と呼ぶ．
2.2
多項式時間アトミック化アルゴリズム
アトミックな NFA を求める多項式時間のアルゴリズムが，V´azquez らによって提案さ れている [8]．これを，Algorithm 1 に示す．Algorithm 1 は，NFA を入力として，そのレプリカを出力するアルゴリズムである．ただし，到達可能な DFA を反転したものを入 力とすると，その出力はアトミックなレプリカとなることが示されている．本論文では， NFA M に Algorithm 1 を適用したものを Atom(M ) と表記する．また，Algorithm 1 を
V´azquez らのアルゴリズムと呼ぶ． Algorithm 1 V´azquez らのアルゴリズム [8] Require: A NFA M = (Q, Σ, δ, I, F ) Ensure: A replica of M 1: I = {I} 2: Q = I 3: δ′ =∅ 4: F = I if I ∩ F ̸= ∅ ∅ otherwise 5: L = I 6: while L ̸= ∅ do
7: Choose and delete P from L
8: for a∈ Σ do
9: P =∧S∈QS| δ(P, a) 10: L = L ∪ (P \ Q)
11: Q = Q ∪ P
12: Add to δ′ the transitions (P, a, S′), where S′ ∈ P
13: F = F ∪ {S ∈ P | S ∩ F ̸= ∅}
14: end for
15: end while
16: Return M′ = (Q, Σ, δ′,I, F)
V´azquez らのアルゴリズムは，NFA から到達可能な DFA を得る部分集合法と似てい
る．しかし，部分集合法では，遷移先状態が既出の状態と異なる場合には，その遷移先を そのまま，出力の新たな状態として追加するのに対して，このアルゴリズムでは，可能な 限り，既出の状態に分割させて状態遷移を追加していく．これを行うのが，Algorithm 1
の 9 行目にある分割と粗分割である．9 行目の分割は，遷移先状態をある既出の状態に含 まれるか否かで分割する操作であり，粗分割は，それらの分割を持ち寄り，より細かく 分割する操作であるとそれぞれ考えることができる． また，7 行目や 8 行目での状態や文字の選択順に制約はない． 例 7. V´azquez らのアルゴリズムの処理過程を図 2.5 に示す．ただし，図 2.5 では，青矢印 の上に示した状態と文字を選択することで，青矢印の先に示すような NFA が順に求まる ことを表しており，また，選択待ちの状態は白で，選択済みの状態は青で塗り分けた．こ こで，入力の NFA M は，Rev(M ) が到達可能な DFA であり，出力はアトミックな NFA となる． はじめに，I = {{0, 1}} となり，L = {{0, 1}} となる．1 回目の while ループで，状態 P ={0, 1} と文字 b を選択することにする．δ({0, 1}, b) = {0, 2} を，既出の状態 {0, 1} で分 割すると，{0, 1} | {0, 2} = {{0}, {2}} となる．既出の状態は {0, 1} しかないため，粗分割 の結果は，この分割の結果{{0}, {2}} と等しく，状態 P = {0, 1} からの文字 b による遷移 先として，状態{0}, {2} が求まる．続いて，文字 a を選択すると，δ({0, 1}, a) = {0, 1, 2, 3} であり，これを既出の状態で分割するとそれぞれ{0, 1} | {0, 1, 2, 3} = {{0, 1}, {2, 3}}， {0} | {0, 1, 2, 3} = {{0}, {1, 2, 3}}，及び {2} | {0, 1, 2, 3} = {{2}, {0, 1, 3}} となる．よっ て，粗分割は以下のように求まる． { {0, 1}, {2, 3}}∧{{0}, {1, 2, 3}}∧{{2}, {0, 1, 3}} ={{{0, 1} ∩ {0}, {0, 1} ∩ {1, 2, 3}, {2, 3} ∩ {0}, {2, 3} ∩ {1, 2, 3}} \ {∅}}∧{{2}, {0, 1, 3}} ={{0}, {1}, {2, 3}}∧{{2}, {0, 1, 3}} ={{{0} ∩ {2}, {0} ∩ {0, 1, 3}, {1} ∩ {2}, {1} ∩ {0, 1, 3}, {2, 3} ∩ {2}, {2, 3} ∩ {0, 1, 3}} \ {∅}} ={{0}, {1}, {2}, {3}} よって，状態 P ={0, 1} からの文字 a による遷移先として，状態 {0}, {1}, {2}, {3} が求 まる． 同様にして，状態{0} 及び文字 a により状態 {1}, {2} が，状態 {0} 及び文字 b により状 態{2} がそれぞれ遷移先として求まる． 以下，状態{1} 及び文字 a により状態 {0}, {3} が，状態 {1} 及び文字 b により状態 {0}
{0,1} {1} 𝑎 𝑎, 𝑏 {2} 𝑎, 𝑏 {3} {0} 𝑎 𝑏 𝑏 𝑎, 𝑏 𝑎, 𝑏 𝑎 𝑎 {0,1} {1} 𝑎 𝑎, 𝑏 {2} 𝑎, 𝑏 {3} {0} 𝑎 {0,1} 𝑏 {2} 𝑏 {0} 0,1 , 𝑏 0,1 , 𝑎 … ：選択済みの状態 ：選択待ちの状態 入力 出力 {0,1} 1 3 𝑎, 𝑏 𝑎 𝑏 0 2 𝑏 𝑎, 𝑏 𝑎 図 2.5: V´azquez らのアルゴリズムの処理過程の例． が，状態{2} 及び文字 b により状態 {1}, {3} が，それぞれ遷移先として求まる．また，状 態{2} 及び文字 a，状態 {3} 及び文字 a，状態 {3} 及び文字 b による遷移先状態はそれぞ れ求まらない． 最終的に，図 2.5 の右下に示す NFA が出力される． Algorithm 1 では，入力が同一であっても，7 行目での状態の選択順や，8 行目での文 字の選択順によって，出力の NFA の状態数が変化する場合がある． 例 8. 図 2.6 は，同じ NFA M を入力とする，例 7 とは異なる Atom(M ) の導出過程である． 図 2.6 では，1 回目の while ループで，状態 P = {0, 1} と文字 a を選択している．そ れにより，状態{0, 1}, {2, 3} が遷移先として求まる．続いて，文字 b を選択して，状態 {0}, {2} が遷移先として求まる．以下同様に処理を進めると，最終的に図 2.6 の右下に示 す NFA が出力される． V´azquez らのアルゴリズムの出力の NFA の状態数について，定理 1 が成り立つ．また，
{0,1} {1} 𝑏 {2} 𝑏 {3} {0} 𝑏 𝑏 𝑎, 𝑏 𝑎, 𝑏 𝑎 𝑎 {2,3} 𝑏 𝑏 𝑎 𝑎 {0,1} {1} 𝑏 {2} 𝑏 {3} {0} {2,3} 𝑏 𝑏 𝑎 {0,1} 𝑏 {2} 𝑏 {0} {2,3} 𝑎 𝑎 {0,1} {2,3} 𝑎 𝑎 0,1 , 𝑎 0,1 , 𝑏 2,3 , 𝑏 … ：選択済みの状態 ：選択待ちの状態 出力 図 2.6: 図 2.5 とは異なる V´azquez らのアルゴリズムの処理過程の例． 2k− 1 となるのは，状態の 2 要素への分割が連続的に生じる場合である [8]．この場合に ついては，第 3 章で説明する．
定理 1 (V´azquez, Garc´ıa, and L´opez [8]). V´azquez らのアルゴリズムの出力の NFA の状
態数は，入力の NFA の状態数を k とすると，高々2k− 1 である．
2.3
DFA
の
Brzozowski
系状態数最小化アルゴリズム
DFA M を入力として，M と等価で最小の DFA を出力する，DFA の状態数最小化ア ルゴリズムの一つを，Algorithm 2 に示す [5]．すなわち，DFA M を入力として，その出 力 Det(Rev(Det(Rev(M )))) は M の最小 DFA である．本アルゴリズムは，NFA M を入 力としても，その出力 Det(Rev(Det(Rev(M )))) は M と等価で最小の DFA である．本論 文では，Algorithm 2 を Brzozowski アルゴリズムと呼ぶ． Algorithm 2 は，その 2 行目の決定性化を，アトミックな NFA を得る操作に置き換え ても，最小化アルゴリズムとして機能する [7]．これを Algorithm 3 に示す．本論文で は，Algorithm 3 の 2 行目のアトミック化に V´azquez らのアルゴリズムを用いたもの， すなわち，DFA M を入力として，Det(Rev(Atom(Rev(M )))) を出力するものを，拡張 Brzozowski アルゴリズムと呼ぶ．
反転 決定性化 決定性化 反転 反転 決定性化 アトミック化 Brzozowski アルゴリズム の適用例 拡張Brzozowski アルゴリズム の適用例 𝑏 𝑎 𝑏 𝑎 𝑎 0 1 2 𝑎 𝑎 𝑏 3 4 𝑏 𝑏 𝑏 𝑎 𝑏 𝑎 𝑎 0 1 2 𝑎 𝑎 𝑏 3 4 𝑏 𝑏 {2} {1,3} 𝑏 {1,2,3} {0,1,2,3,4} 𝑎 𝑏 𝑎 𝑎, 𝑏 {0,2,4} 𝑎 𝑎 {0,1,3,4} 𝑏 𝑏 𝑎 ∅ 𝑏 𝑎, 𝑏 𝑏 𝑎 𝑎, 𝑏 𝑎 { 0,1,3,4 , 0,1,2,3,4 , {0,2,4}} 𝑏 { 1,2,3 , 0,1,2,3,4 , 0,1,3,4 , {1,3}} { 1,2,3 , 0,1,2,3,4 , 0,2,4 , {2}} 𝑏 𝑎 𝑎, 𝑏 𝑎 {{0,4}} { 1,2,3 , 1,3 } 𝑏 { 1,2,3 , 2 } {2} {1,3} 𝑎 𝑎, 𝑏 𝑎 {1,2,3} {0,4} 𝑏 𝑎 𝑎, 𝑏 𝑎 𝑏 {2} {1,3} 𝑎 𝑎, 𝑏 𝑎 {1,2,3} {0,4} 𝑏 𝑎 𝑎, 𝑏 𝑎 𝑏 {2} {1,3} 𝑏 {1,2,3} {0,1,2,3,4} 𝑎 𝑏 𝑎 𝑎, 𝑏 {0,2,4} 𝑎 𝑎 {0,1,3,4} 𝑏 𝑏 𝑎 ∅ 𝑏 𝑎, 𝑏 図 2.7: Brzozowski アルゴリズムと拡張 Brzozowski アルゴリズムの適用例．
Algorithm 2 Brzozowski アルゴリズム [5] Require: A DFA M
Ensure: Minimal DFA of M
1: Obtain M1 = Rev(M ) 2: Obtain M2 = Det(M1) 3: Obtain M3 = Rev(M2) 4: Return M′ = Det(M3) Algorithm 3 拡張 Brzozowski アルゴリズムの一般形 [7] Require: A DFA M
Ensure: Minimal DFA of M
1: Obtain M1 = Rev(M )
2: Obtain M2, an atomic NFA equivalent to M1
3: Obtain M3 = Rev(M2) 4: Return M′ = Det(M3) 例 9. Brzozowski アルゴリズムと拡張 Brzozowski アルゴリズムの適用例を図 2.7 示す．図 2.7 では，最上部にある DFA を両アルゴリズムの共通の入力とし，左側に Brzozowski ア ルゴリズムの適用例を，右側に拡張 Brzozowski アルゴリズムの適用例をそれぞれ示した． 最下部にある両アルゴリズムの出力は，共に状態数 3 の DFA となっており，状態名の違 いを除けば同じ DFA である． Brzozowski アルゴリズムと拡張 Brzozowski アルゴリズムの違いは，1 回目の反転の次 に，決定性のものを求めるか，アトミックなものを求めるかである．そこで，それぞれ を適用した後の状態数，すなわち 2 回目の反転の前の状態数に着目する． 決定性のものを求める場合，入力の NFA M の状態数を k とすると，出力 Det(M ) の 状態数は高々2kである．2kとなるのは，出力 Det(M ) の状態が，入力 M の各状態の組 み合わせを網羅する，図 2.8 に示すような場合である．対して，V´azquez らのアルゴリズ ムを用いてアトミックなものを求める場合，入力の NFA M の状態数を k とすると，出 力 Atom(M ) の状態数は高々2k − 2 である．ここで，V´azquez らのアルゴリズムの出力 の状態数は高々2k− 1 であるが，DFA を反転したものを入力とすると，2k − 1 となる場
決定性化 入力 出力 0 𝑐 𝑎, 𝑏 1 𝑎 𝑎 2 𝑎, 𝑏 {0,1,2} {0,1} {0,2} {1,2} {1} {0} {2} ∅ 𝑎 𝑎 𝑎 𝑎 𝑎 𝑐 𝑐 𝑐 𝑐 𝑐 𝑎, 𝑏, 𝑐 𝑎, 𝑏, 𝑐 𝑏 𝑏 𝑏 𝑏 𝑏 𝑎 𝑏 𝑐 図 2.8: 決定性化の出力の状態数が最大となる例． 合は存在しない．これは第 3 章で示す． したがって，拡張 Brzozowski アルゴリズムでは，Brzozowski アルゴリズムに対して， 途中の NFA の状態数を大きく削減できる可能性があり，両アルゴリズムの最悪時計算量 を比べると，Brzozowski アルゴリズムは指数時間であるのに対して，拡張 Brzozowski ア ルゴリズムは多項式時間である [8]．
第
3
章
V´
azquez
らのアルゴリズムの出力の状態数の解析
定理 1 により，V´azquez らのアルゴリズムの出力の NFA の状態数は，入力の NFA の
状態数を k とすると，高々2k− 1 である．また，2k − 1 となるのは，状態の 2 要素への 分割が連続的に生じる場合である [8]．[8] では，出力の状態数が最大となる入力例につい てや，到達可能な DFA を反転したものが入力の場合に，出力の状態数がどうなるかにつ いては述べられていなかった．そこで，本章では，任意の NFA を入力とする場合と，到 達可能な DFA を反転したものを入力とする場合に分けて，その出力の状態数の最大値と 最小値，及び出力の状態数が最大や最小となる入力例について述べる． 本章の以下の議論において，特に断らない限り，V´azquez らのアルゴリズムの入力の NFA を M = (Q, Σ, δ, I, F ) とし，出力の NFA を M′ = (Q′, Σ, δ′, I′, F′) とする．また， |Q| = k とする．
3.1
任意の
NFA
を入力とする場合の出力の最大状態数
V´azquez らのアルゴリズムの出力の状態数|Q′| が 2k − 1 となる場合について，[8] の指 摘を言い換えると観察 1 のようになる． 観察 1. V´azquez らのアルゴリズムの出力の状態数|Q′| が 2k − 1 となるのは，入力の状 態集合 Q を，Q の空でない真部分集合 R⊊ Q 及び S = Q \ R の 2 要素に分割し，それら の部分集合をこれ以上分割ができない単集合になるまで同様に 2 分割する操作を繰り返 すときの，分割前と分割後の全ての部分集合と Q の集合に，出力の状態集合 Q′が等しい 場合である．{0,1,2,3,4} {0} 𝑏 𝑎 {1,2,3,4} 𝑎 {4} {1,2,3} 𝑏 {2,3} {1} 𝑏 {2} 𝑏 𝑎 {3} 𝑏 𝑎, 𝑏 𝑎 𝑏 𝑏 𝑏 𝑏 𝑎 𝑎 𝑎 𝑎 𝑎 𝑏 𝑏 𝑏 𝑎 𝑏 入力 出力 𝑏 𝑎 𝑏 𝑎 𝑏 0 1 2 𝑎 𝑏 𝑎 3 4 Vázquezらの アルゴリズム 図 3.1: V´azquez らのアルゴリズムの出力の状態数が 2k− 1 となる具体例． 例 10. V´azquez らのアルゴリズムの出力の状態数が 2k− 1 となる具体例を図 3.1 に示す． この例は，k = 5 であるが，確かに出力 Atom(M ) の状態数は 2k− 1 = 9 である．観察 1 で述べたように，出力の状態集合 Q′は，{0, 1, 2, 3, 4}，{0, 1, 2, 3, 4} を 2 分割した {0} 及 び{1, 2, 3, 4}，{1, 2, 3, 4} を 2 分割した {1, 2, 3} 及び {4}，{1, 2, 3} を 2 分割した {1} 及び {2, 3}，{2, 3} を 2 分割した {2} 及び {3} を元とする， Q′ ={{0, 1, 2, 3, 4}, {0}, {1, 2, 3, 4}, {1, 2, 3}, {4}, {1}, {2, 3}, {2}, {3}} となっている． また，結果として観察 1 に示すような状態が得られれば良く，各状態から分割先の状 態への遷移がある必要はないこともわかる．例えば，図 3.1 では状態{1, 2, 3, 4} から状態 {1, 2, 3} に向かう遷移は存在しない． V´azquez らのアルゴリズムの出力の状態数|Q′| が 2k − 1 となる入力に関して，補題 1 が成り立つ． 補題 1. V´azquez らのアルゴリズムの出力の状態数|Q′| が 2k − 1 となるためには，その 入力の状態全てが初期状態，すなわち Q = I である必要がある．
証明. 補題 1 の対偶を示す． 入力の NFA M の状態集合 Q に初期状態でない状態も含まれるとき，初期状態でない 状態の集合を R = Q\ I ̸= ∅ とする. NFA M に V´azquez らのアルゴリズムを適用する と，出力の初期状態は状態 I となる．本アルゴリズムの処理過程で Algorithm 1 の 9 行 目が δ(P, a) = Q となった場合，Q は，既出の状態 I によって状態 I と状態 R に分割さ れるため，状態 Q が出力の状態として追加されることはない．観察 1 より，出力の状態 数|Q′| が 2k − 1 となるためには，Q ∈ Q′の必要があるが，状態 Q が出力の状態として 追加されることはないから，出力の状態数|Q′| は高々2k − 2 となり，2k − 1 となること はない． 3.1.1 |Σ| = 1 のとき |Σ| = 1 のとき，V´azquez らのアルゴリズムの出力の状態数について，定理 2 が成り 立つ． 定理 2. |Σ| = 1, k ≥ 2 のとき，V´azquez らのアルゴリズムの出力の状態数 |Q′| について， |Q′| ≤ 2k − 2 が成り立つ．またこの上界は厳密である． 証明. はじめに，出力の状態数|Q′| について，|Q′| ≤ 2k − 2 が成り立つことを示す．定 理 1 により，V´azquez らのアルゴリズムの出力の状態数|Q′| は高々2k − 1 であるから， |Σ| = 1, k ≥ 2 のとき，本アルゴリズムの出力の状態数 |Q′| が 2k − 1 となる入力 M が存 在すると仮定し，Σ ={a} とする．補題 1 により，M はその状態全てが初期状態，すな わち Q = I である．よって，M に本アルゴリズムを適用すると，状態 Q が出力の初期状 態として求まる． Q からの遷移先 δ(Q, a) が Q と等しい，すなわち δ(Q, a) = Q のとき，新たな状態は追加 されず，アルゴリズムは停止する．この場合の出力の状態数|Q′| は 1 であり，|Q′| = 2k−1 という仮定に矛盾する． Q からの遷移先 δ(Q, a) が Q と異なる，すなわち δ(Q, a) ̸= Q のとき，新たな状態 B = δ(Q, a) が追加される．ここで，状態 B には M の全ての状態からの遷移先状態が含 まれており，ゆえに以後の処理過程のある状態 C からの遷移先 δ(C, a) が，状態 B に含 まれない状態 D = Q\ B を含むことはない（∀C ⊆ Q, D ⊈ δ(C, a)）．よって，状態 D が
図 3.2: |Σ| = 1 のとき，V´azquez らのアルゴリズムの出力の状態数が 2k − 2 となる入 力例． 新たな状態として追加されることはなく，アルゴリズムは停止する．観察 1 より，出力 の状態集合 Q′には状態 D も含まれるはずであり，矛盾が生じる． したがって，|Σ| = 1, k ≥ 2 のとき，V´azquez らのアルゴリズムの出力の状態数 |Q′| が 2k− 1 となる入力は存在せず，|Q′| は高々2k − 2 となる． 次に，上界が厳密であることを示す．V´azquez らのアルゴリズムの出力の状態数が 2k−2 となる入力例を，図 3.2 に示し，この NFA を M とする．ただし，状態の選択順は，含ま れる M の状態が多い順とする．M に本アルゴリズムを適用すると，状態{0, 1, ..., k − 2} が出力の初期状態として求まる．続いて，状態{0, 1, 2, ..., k − 2} から文字 a による遷移 先として状態{1, 2, .., k − 2}, {k} が追加される．状態 {1, 2, .., k − 2} と {k} を比較して， 含まれる M の状態が多い方として状態{1, 2, .., k − 2} を選択すると，文字 a による遷移 先として状態{2, .., k − 2} が追加される．同様にして，状態の選択と新たな状態の追加 を繰り返すと，状態{k − 1} が未選択の状態として残る．状態 {k − 1} を選択すると，状 態{0} が新たな状態として追加される．同様にして，状態 {1}, {2}, ..., {k − 3} が追加さ れる．以上のようにして，観察 1 で述べた状態集合から入力 M の状態集合 Q を除いたも のを状態集合として持つ出力が得られる． 例 11. |Σ| = 1 のとき，V´azquez らのアルゴリズムの出力の状態数が 2k − 2 となる具体 例を図 3.3 に示す． 図 3.2 で示した入力例は，k ≤ 4 のときは，状態の選択順によらず，出力の状態数が 2k− 2 となるものである．
{0,1,2,3} 𝑎 {1,2,3} {4} 𝑎 {0,1,2,3} 𝑎 {1,2,3} {2,3} {4} 𝑎 𝑎 𝑎 {0,1,2,3} {0} 𝑎 {1,2,3} {2,3} {1} 𝑎 {4} 𝑎 𝑎 𝑎 𝑎 𝑎 {3} {2} 𝑎 𝑎 𝑎 𝑎 {0,1,2,3} 𝑎 {1,2,3} {2,3} {4} 𝑎 𝑎 𝑎 𝑎 {3} 𝑎 {0,1,2,3} 𝑎 {1,2,3} {2,3} {4} 𝑎 𝑎 𝑎 𝑎 {3} 𝑎 𝑎 {0,1,2,3} {0} 𝑎 {1,2,3} {2,3} {4} 𝑎 𝑎 𝑎 𝑎 𝑎 {3} 𝑎 𝑎 {0,1,2,3} {0} 𝑎 {1,2,3} {2,3} {1} 𝑎 {4} 𝑎 𝑎 𝑎 𝑎 𝑎 {3} 𝑎 𝑎 {0,1,2,3} {0} 𝑎 {1,2,3} {2,3} {1} 𝑎 {4} 𝑎 𝑎 𝑎 𝑎 𝑎 {3} {2} 𝑎 𝑎 𝑎 入力 2 1 4 0 3 1,2,3 2,3 0,1,2,3 出力 3 𝑎 𝑎 0 1 2 𝑎 3 𝑎 𝑎 4 {0,1,2,3} 図 3.3: |Σ| = 1 のとき，V´azquez らのアルゴリズムの出力の状態数が 2k − 2 となる具 体例． 3.1.2 |Σ| ≥ 2 のとき |Σ| ≥ 2 のとき，V´azquez らのアルゴリズムの出力の状態数について，定理 3 が成り 立つ． 定理 3. |Σ| ≥ 2 のとき，V´azquez らのアルゴリズムの出力の状態数 |Q′| について，|Q′| ≤ 2k− 1 が成り立つ．またこの上界は厳密である． 証明. はじめに，出力の状態数|Q′| について，|Q′| ≤ 2k − 1 が成り立つことは，定理 1 にある．ここでは，この上界が厳密であることを示す．V´azquez らのアルゴリズムの出 力の状態数が 2k− 1 となる入力例を，図 3.4 に示し，この NFA を M とする．ただし，状 態の選択順は，含まれる M の状態が多い順とし，文字の選択は a, b の順とする．M に本 アルゴリズムを適用すると，状態{0, 1, 2, ..., k − 1} が出力の初期状態として求まる．続 いて，状態{0, 1, 2, ..., k − 1} から文字 a による遷移先として状態 {1, 2, .., k − 1} が追加 される．また，状態{0, 1, 2, ..., k − 1} から文字 b による遷移先として状態 {0} が追加さ れる．状態{1, 2, .., k − 1} 及び {0} を比較して，含まれる M の状態が多い方として状態 {1, 2, .., k − 1} を選択すると，文字 a による遷移先として状態 {2, .., k − 1} が，文字 b に よる遷移先として状態{1} がそれぞれ追加される．同様にして，選択した状態 q0の，部
図 3.4: |Σ| = 2 のとき，V´azquez らのアルゴリズムの出力の状態数が 2k − 1 となる入 力例． 分集合である単集合 q1とそれ以外 q2 = q0\ q1への 2 分割と，それら状態の追加が繰り返 される．以上のようにして，観察 1 で述べた状態集合を持つ出力が得られる． |Σ| ≥ 3 のときは，文字 a による遷移は図 3.4 の a による遷移と同じとし，a 以外の文 字による遷移は図 3.4 の b による遷移と同じとして，同様に証明できる． 例 12. |Σ| = 2 のとき，V´azquez らのアルゴリズムの出力の状態数が 2k − 1 となる具体 例を図 3.5 に示す．
3.2
到達可能な
DFA
を反転したものを入力とする場合の出力の最大状
態数
到達可能な DFA を反転したものを入力とする場合には，出力の状態数にも制約が生じ る．この場合の V´azquez らのアルゴリズムの出力の状態数について，定理 4 が成り立つ． 定理 4. 到達可能な DFA を反転したものを入力とする場合，入力の状態数 k≥ 2 のとき， V´azquez らのアルゴリズムの出力の状態数|Q′| は，高々2k − 2 である． 証明. 定理 1 により，V´azquez らのアルゴリズムの出力の状態数|Q′| は，どんな NFA を入 力としても，高々2k−1である．そこで，到達可能なDFAを反転したものを入力とし，k ≥ 2 のときに，本アルゴリズムの出力の状態数|Q′| が 2k − 1 となる入力 M = (Q, Σ, δ, I, F ) が存在すると仮定する．補題 1 により，M はその状態全てが初期状態，すなわち Q = I である．よって，M に本アルゴリズムを適用すると，状態 Q が出力の初期状態として求 まる．{0,1,2,3,4} {0} 𝑏 𝑎, 𝑏 {1,2,3,4} 𝑎, 𝑏 {2,3,4} {1} 𝑏 {0,1,2,3,4} {0} 𝑏 𝑎, 𝑏 {1,2,3,4} 𝑎 {2, 3,4} {0,1,2,3,4} {0} 𝑏 𝑎, 𝑏 {1,2,3,4} {0,1,2,3,4} 𝑎 {1,2,3,4} {0,1,2,3,4} {0,1,2,3,4} {0} 𝑏 𝑎, 𝑏 {1,2,3,4} 𝑎, 𝑏 {2,3,4} {1} 𝑏 𝑎 {3,4} {0,1,2,3,4} {0} 𝑏 𝑎, 𝑏 {1,2,3,4} 𝑎, 𝑏 {2,3,4} {1} 𝑏 {2} 𝑏 𝑎, 𝑏 {3,4} {0,1,2,3,4} {0} 𝑏 𝑎, 𝑏 {1,2,3,4} 𝑎, 𝑏 {2,3,4} {1} 𝑏 {2} 𝑏 𝑎, 𝑏 {3,4} 𝑎, 𝑏 {4} {3} 𝑏 {0,1,2,3,4} {0} 𝑏 𝑎, 𝑏 {1,2,3,4} 𝑎, 𝑏 {2,3,4} {1} 𝑏 {2} 𝑏 𝑎, 𝑏 {3,4} 𝑎 {4} {0,1,2,3,4} {0} 𝑏 𝑎, 𝑏 {1,2,3,4} 𝑎, 𝑏 {2,3,4} {1} 𝑏 {2} 𝑏 𝑎, 𝑏 {3,4} 𝑎, 𝑏 {4} {3} 𝑏 𝑎 𝑎 𝑎 𝑎 𝑏 𝑎, 𝑏 𝑏 𝑏 𝑏 𝑏 𝑎 𝑏 𝑎 𝑏 0 1 2 𝑎 𝑏 𝑎 𝑎, 𝑏 3 4 入力 2,3,4 , 𝑎 1,2,3,4 , 𝑏 3,4 , 𝑏 3,4 , 𝑎 … 2,3,4 , 𝑏 1,2,3,4 , 𝑎 0,1,2,3,4 , 𝑏 0,1,2,3,4 , 𝑎 出力 図 3.5: |Σ| = 2 のとき，V´azquez らのアルゴリズムの出力の状態数が 2k − 1 となる具 体例．
ここで，Rev(M ) = (Q, Σ, δR, F, I) は到達可能な DFA であるから，Rev(M ) の状態全
てが，各文字による状態遷移元である（∀q ∈ Q, ∀a ∈ Σ, ∃p ∈ Q, δR(q, a) = p）．ゆえに， M の状態全てが，各文字による状態遷移先である（∀q ∈ Q, ∀a ∈ Σ, ∃p ∈ Q, δ(p, a) = q）． よって，出力の初期状態 Q からの遷移先は，どの文字によっても状態 Q となり（∀a ∈ Σ, δ(Q, a) = Q），新たな状態は追加されずアルゴリズムは停止する．この場合の出力の 状態数|Q′| は 1 であり，|Q′| = 2k − 1 という仮定に矛盾する． したがって，到達可能な DFA を反転したものを入力とし，k ≥ 2 のとき，V´azquez ら のアルゴリズムの出力の状態数|Q′| が 2k − 1 となる入力は存在せず，|Q′| は高々2k − 2 となる． 到達可能な DFA を反転したものを入力とし，V´azquez らのアルゴリズムの出力の状態 数|Q′| が 2k − 2 となる場合について，観察 2 が言える． 観察 2. 到達可能な DFA を反転したものを入力とし，V´azquez らのアルゴリズムの出力 の状態数|Q′| が 2k − 2 となる入力 M が存在するならばそれは，入力の状態集合 Q を，Q
の空でない真部分集合 R⊊ Q 及び S = Q \ R の 2 要素に分割し，それらの部分集合をこ れ以上分割ができない単集合になるまで同様に 2 分割する操作を繰り返すときの，分割 前と分割後の全ての部分集合の（Q を含まない）集合に，出力の状態集合 Q′が等しい場 合である． 証明. 到達可能な DFA を反転したものを入力とし，V´azquez らのアルゴリズムの出力の 状態数|Q′| が 2k − 2 となる出力の状態集合 Q′として考えられるのは，観察 2 で述べたも のか，観察 1 で述べたものから状態 Q 以外を除いたものの 2 通りである． 後者について，定理 4 の証明にあるように，本アルゴリズムで状態 Q が出力の初期状 態として求まる場合の，出力の状態数|Q′| は 1 である．また，補題 1 の証明にあるよう に，初期状態としてでなく，状態 Q を後から追加することはできない．よって，後者の ような状態集合 Q′をもつ出力は存在しない． 例 13. 到達可能な DFA を反転したものを入力とし，V´azquez らのアルゴリズムの出力 の状態数が 2k− 2 となる具体例を図 3.6 に示す．この例は，k = 4 であるが，確かに出 力 Atom(M ) の状態数は 2k− 2 = 6 である．観察 2 で述べたように，出力の状態集合 Q′ は，状態{0, 1, 2, 3} を 2 分割した {0, 1}, {2, 3}，状態 {0, 1} を 2 分割した {0}, {1}，状態 {2, 3} を 2 分割した {2}, {3} を元とする， Q′ ={{0, 1}, {2, 3}, {0}, {1}, {2}, {3}} となっている． また，結果として観察 2 に示すような状態が得られれば良く，各状態から分割先の状 態への遷移がある必要はないこともわかる．例えば，図 3.6 では状態{0, 1} から {1} に向 かう遷移，状態{2, 3} から {2} に向かう遷移は，それぞれ存在しない． 3.2.1 |Σ| = 1 のとき 到達可能な DFA を反転したものを入力とし，|Σ| = 1 のとき，V´azquez らのアルゴリ ズムの出力の状態数について，定理 5 が成り立つ．
{0,1} {1} 𝑏 {2} 𝑏 {3} {0} 𝑏 𝑏 𝑎, 𝑏 𝑎, 𝑏 𝑎 𝑎 {2,3} 𝑏 𝑏 𝑎 𝑎 1 3 𝑎, 𝑏 𝑎 𝑏 0 2 𝑏 𝑎, 𝑏 𝑎 入力 出力 Vázquezらの アルゴリズム 図 3.6: 到達可能な DFA を反転したものを入力とし，V´azquez らのアルゴリズムの出力 の状態数が 2k− 2 となる具体例． 図 3.7: 到達可能な DFA を反転したもので，|Σ| = 1 のとき，V´azquez らのアルゴリズム の出力の状態数が 2k− 2 となる入力例． 定理 5. 到達可能な DFA を反転したものを入力とし，|Σ| = 1, k ≥ 2 のとき，V´azquez ら のアルゴリズムの出力の状態数|Q′| について，|Q′| ≤ 2k − 2 が成り立つ．またこの上界 は厳密である． 証明. はじめに，出力の状態数|Q′| について，|Q′| ≤ 2k − 2 が成り立つことは，定理 4 にある．ここでは，この上界が厳密であることを示す．到達可能な DFA を反転したもの で，V´azquez らのアルゴリズムの出力の状態数が 2k− 2 となる入力例を，図 3.7 に示し，
この NFA を M とする．M を反転したもの Rev(M ) は，到達可能な DFA であり，入力 条件を満たしている．ただし，状態の選択順は，含まれる M の状態が多い順とする．こ の M は，図 3.2 に示すものと同じであり，定理 2 の証明に示したように，M に V´azquez
らのアルゴリズムを適用した出力の状態数は，2k− 2 になる．
例 14. 到達可能な DFA を反転したものを入力とし，|Σ| = 1 のとき，V´azquez らのアル
図 3.8: 到達可能な DFA を反転したもので，|Σ| = 1, k = 5 のとき，状態の選択順によら ず V´azquez らのアルゴリズムの出力の状態数が 2k− 2 = 8 となる入力例． 図 3.7 で示した入力例は，k ≤ 4 のときは，状態の選択順によらず，その出力の状態数 は 2k− 2 となる． 図 3.7 に対して，k = 5 で状態の選択順によらず，出力の状態数が 2k− 2 = 8 となる入 力例を，図 3.8 に示す．また，図 3.8 の NFA に V´azquez らのアルゴリズムを適用した場 合に起こりうる，全ての処理過程を図 3.9 に示す． 3.2.2 |Σ| ≥ 2 のとき 到達可能な DFA を反転したものを入力とし，|Σ| ≥ 2 のとき，V´azquez らのアルゴリ ズムの出力の状態数について，定理 6 が成り立つ． 定理 6. 到達可能な DFA を反転したものを入力とし，|Σ| ≥ 2, k ≥ 2 のとき，V´azquez ら のアルゴリズムの出力の状態数|Q′| について，|Q′| ≤ 2k − 2 が成り立つ．またこの上界 は厳密である． 証明. はじめに，出力の状態数|Q′| について，|Q′| ≤ 2k − 2 が成り立つことは，定理 4 に ある．ここでは，この上界が厳密であることを示す．到達可能な DFA を反転したもので， V´azquez らのアルゴリズムの出力の状態数が 2k−2 となる入力例を，図 3.10 に示し，この
NFA を M とする．M を反転したもの Rev(M ) は，到達可能な DFA であり，入力条件を 満たしている．ただし，状態の選択順は，含まれる M の状態が多い順とし，文字の選択 順は任意とする．M に本アルゴリズムを適用すると，状態{0, 1, 2, ..., k −2} が出力の初期 状態として求まる．文字の選択は a, b の順とすると，状態{0, 1, 2, ..., k − 2} から文字 a に よる遷移先として状態{1, 2, .., k −2}, {k −1} が追加される．また，状態 {0, 1, 2, ..., k −2} から文字 b による遷移先として状態{0} が追加される．状態 {1, 2, .., k − 2}，{k − 1}，及 び{0} を比較して，含まれる M の状態が多い状態 {1, 2, .., k − 2} を選択すると，文字 a による遷移先として状態{2, .., k − 2} が，文字 b による遷移先として状態 {1} がそれぞ
図 3.9: 図 3.8 の NFA に V´azquez らのアルゴリズムを適用した場合に起こりうる，全て の処理過程．
図 3.10: 到達可能な DFA を反転したもので，|Σ| = 2 のとき，V´azquez らのアルゴリズ ムの出力の状態数が 2k− 2 となる入力例． れ追加される．同様にして，選択した状態 q0の，部分集合である単集合 q1とそれ以外の q2 = q0\ q1への 2 分割と，それら状態の追加が繰り返される．以上のようにして，観察 2 で述べた状態集合を持つ出力が得られる． |Σ| ≥ 3 のときは，文字 a による遷移は図 3.10 の a による遷移と同じとし，a 以外の文 字による遷移は図 3.10 の b による遷移と同じとして，同様に証明できる． 例 15. 到達可能な DFA を反転したものを入力とし，|Σ| = 2 のとき，V´azquez らのアル ゴリズムの出力の状態数が 2k− 2 となる具体例を図 3.11 に示す． 図 3.2 で示した入力例は，k ≤ 4 のときは，状態の選択順によらず，その出力の状態数 は 2k− 2 となる．
3.3
V´
azquez
らのアルゴリズムの出力の状態数
V´azquez らのアルゴリズムの出力の最大状態数についてまとめると，表 3.1 のようにな る．表 3.1 でマスが 2 段となっているところは，上段が，出力の状態数の最大値を表し， 下段が，出力の状態数が最大となる（現在見つかっている）入力例の，本アルゴリズム 適用時の状態や文字の選択順の指定の有無を表す． また，V´azquez らのアルゴリズムの出力の最小状態数について，定理 7 が成り立つ． 定理 7. 入力が任意の NFA であっても，到達可能な DFA を反転したものであっても， |Σ| ≥ 1, k ≥ 1 のとき，V´azquez らのアルゴリズムの出力の状態数 |Q′| について，|Q′| ≥ 1 が成り立つ．またこの下界は厳密である．{0,1,2,3} {0,1,2,3} 𝑎 {1,2,3} {4} 𝑎 {0,1,2,3} {0} 𝑎 {1,2,3} {4} 𝑎, 𝑏 𝑏 𝑎 𝑎 0 1 2 𝑎 3 𝑎 𝑏 𝑏 𝑏 𝑏 𝑎 4 𝑏 {0,1,2,3} {0} 𝑎 {1,2,3} {2,3} {4} 𝑎 𝑎, 𝑏 𝑎 𝑏 {0,1,2,3} {0} 𝑎 {1,2,3} {2,3} {1} {4} 𝑎, 𝑏 𝑎, 𝑏 𝑎 𝑏 𝑏 {0,1,2,3} {0} 𝑎 {1,2,3} {2,3} {1} {4} 𝑎, 𝑏 𝑎, 𝑏 𝑎 𝑎 {3} 𝑎 𝑏 𝑏 {0,1,2,3} {0} 𝑎 {1,2,3} {2,3} {1} {4} 𝑎, 𝑏 𝑎, 𝑏 𝑎 𝑎 {3} {2} 𝑎, 𝑏 𝑏 𝑏 𝑏 {0,1,2,3} {0} 𝑎 {1,2,3} {2,3} {1} 𝑎 {4} 𝑎, 𝑏 𝑎, 𝑏 𝑎 𝑎 𝑎 {3} {2} 𝑎 𝑎 𝑎, 𝑏 𝑎 𝑏 𝑏 𝑏 𝑏 𝑏 𝑏 𝑏 𝑏 入力 … 1,2,3 , 𝑎 2,3 , 𝑏 2,3 , 𝑎 1,2,3 , 𝑏 0,1,2,3 , 𝑏 0,1,2,3 , 𝑎 出力 図 3.11: 到達可能な DFA を反転したものを入力とし，|Σ| = 2 のとき，V´azquez らのア ルゴリズムの出力の状態数が 2k− 2 となる具体例． 表 3.1: V´azquez らのアルゴリズムの出力の最大状態数 入力 M の 任意の入力 M 到達可能な DFA を反転した入力 M 状態数 k |Σ| = 1 |Σ| ≥ 2 |Σ| ≥ 1 1 1 1 1 2≤ k ≤ 5 2k− 2 2k− 1 2k− 2 （選択順指定無）（選択順指定有） （選択順指定無） k≥ 6 2k− 2 2k− 1 2k− 2 （選択順指定有）（選択順指定有） （選択順指定有）
図 3.12: |Σ| = 1 のとき，V´azquez らのアルゴリズムの出力の状態数が 1 となる入力例． 証明. |Σ| = 1 のとき，V´azquez らのアルゴリズムの出力の状態数が 1 となる入力例を，図 3.12 に示し，この NFA を M1とする．ここで，M1を反転した Rev(M1) は，到達可能な DFA である．また，M1に本アルゴリズムを適用する場合の状態の選択順は一意である． M1に本アルゴリズムを適用すると，M1の状態集合 Q が出力の初期状態として求まる． 状態 Q から文字 a による遷移先は状態 Q であり，新たな状態は生成されない．よって， アルゴリズムは終了し，出力の NFA はその状態集合 Q′ ={Q}，すなわち |Q′| = 1 であ るものとなる． |Σ| = 2 のとき，V´azquez らのアルゴリズムの出力の状態数が 1 となる入力例を，図 3.13 に示し，この NFA を M2とする．ここで，M2を反転した Rev(M2) は，到達可能な DFA である．また，M2に本アルゴリズムを適用する場合の状態の選択順は一意であり， 文字の選択順は任意とする． M2に本アルゴリズムを適用すると，M2の状態集合 Q が出力の初期状態として求まる． 状態 Q から文字 a による遷移先は状態 Q であり，新たな状態は生成されない．また，状 態 Q から文字 b による遷移先も状態 Q であり，新たな状態は生成されない．よって，ア ルゴリズムは終了し，出力の NFA はその状態集合 Q′ ={Q}，すなわち |Q′| = 1 である ものとなる． |Σ| ≥ 3 のときは，文字 a による遷移は図 3.13 の a による遷移と同じとし，a 以外の文 字による遷移は図 3.13 の b による遷移と同じとして，同様に証明できる 例 16. |Σ| = 1 のとき，V´azquez らのアルゴリズムの出力の状態数が 1 となる具体例を図 3.14 に示す．同様に，|Σ| = 2 のとき，V´azquez らのアルゴリズムの出力の状態数が 1 と なる具体例を図 3.15 に示す．
図 3.13: |Σ| = 2 のとき，V´azquez らのアルゴリズムの出力の状態数が 1 となる入力例． {0,1,2,3,4} 0,1,2,3,4 {0,1,2,3,4} 入力 出力 図 3.14: |Σ| = 1 のとき，V´azquez らのアルゴリズムの出力の状態数が 1 となる具体例． {0,1,2,3,4} {0,1,2,3,4} 0,1,2,3,4 , 𝑎 入力 出力 {0,1,2,3,4} 0,1,2,3,4 , 𝑏 図 3.15: |Σ| = 2 のとき，V´azquez らのアルゴリズムの出力の状態数が 1 となる具体例．
第
4
章
V´
azquez
らのアルゴリズムの出力の平均状態数の
削減
Brzozowski 系アルゴリズムでは，2 番目の操作（決定性化及びアトミック化）の出力 の状態数が，全体の計算量に影響する．そこで，本章では，V´azquez らのアルゴリズムで 任意性のある，状態と文字の選択順の工夫による，出力の平均状態数の削減の検討とそ の実験結果を述べる．また，拡張 Brzozowski アルゴリズムを用いることで，Brzozowski アルゴリズムの場合よりも，2 番目の操作の出力の状態数を削減できることを，実験的に 確認した結果も示す．4.1
出力の平均状態数を削減するため検討
V´azquez らが提案した Algorithm 1 では，7 行目の状態 P の選択順及び 8 行目の文字 a の選択順は任意であった．そこで，それらの選択順を工夫することで，出力の平均状態 数を削減できないかと考えた． 図 4.1 は，図 2.5 及び 2.6 と同じ例であるが，文字の選択順で出力の状態数が異なる V´azquez らのアルゴリズムの適用例である．図 4.1 の上部に示した例は，下部に示した例 に対して，状態{2, 3} の分だけ状態が多くなっており，下部の例では，上部の例の状態 {2, 3} の役割を，状態 {2}, {3} で担っているといえる．そこで，状態 {2, 3}, {2}, 及び {3} が出現した様子を観察すると，上部の例では，状態{2, 3} の後に状態 {2}, {3} が出現し ているのに対して，下部の例では，先に状態{2} ⊂ {2, 3} が出現することで，状態 {2, 3} への遷移に相当するものが，状態{2}, {3} に分割遷移されたといえる．以上の観察から，{0,1} {0,1} 𝑏 {2} 𝑏 {0} {0,1} {2,3} 𝑎 𝑎 {0,1} {1} 𝑎 𝑎, 𝑏 {2} 𝑎, 𝑏 {3} {0} 𝑎 {0,1} {1} 𝑏 {2} 𝑏 {3} {0} 𝑏 𝑏 𝑎, 𝑏 𝑎, 𝑏 𝑎 𝑎 {2,3} 𝑏 𝑏 𝑎 𝑎 {0,1} 𝑏 {2} 𝑏 {0} {2,3} 𝑎 𝑎 {0,1} {1} 𝑎 𝑎, 𝑏 {2} 𝑎, 𝑏 {3} {0} 𝑎 𝑏 𝑏 𝑎, 𝑏 𝑎, 𝑏 𝑎 𝑎 𝛿 0,1 , 𝑎 = {0,1,2,3} 𝛿 0,1 , 𝑏 = {0,2} 状態{2,3}が {2}と{3}に分割 2 ⊂ {2,3} 𝛿 0,1 , 𝑏 = {0,2} 𝛿 0,1 , 𝑎 = {0,1,2,3} … … 状態{2,3}が余分 ：選択済みの状態 ：選択待ちの状態 入力 1 3 𝑎, 𝑏 𝑎 𝑏 0 2 𝑏 𝑎, 𝑏 𝑎 出力 図 4.1: 文字の選択順で出力の状態数が異なる，V´azquez らのアルゴリズムの適用例． サイズの小さい状態を先に出現させれば，出力の状態数を小さくできる可能性が高いと 考えた．すなわち，Algorithm 1 のP の元を，よりサイズの小さい状態にできればよいと 考えた． 続いて，Algorithm 1 のP の元を，よりサイズの小さい状態にするための方策につい て，状態 P や文字 a の選択順を変えることで制御できるのは δ(P, a) であるが，δ(P, a) の サイズが小さいほど，P に追加される状態が小さくなる可能性が高いと考えた．これは， 次の分割の対比から予想できる． {0, 1} | {0, 1, 2} ={{0, 1}, {2}} {0, 1} | {0, 1, 2, 3, 4, 5} ={{0, 1}, {2, 3, 4, 5}} 最後に，δ(P, a) のサイズを小さくするための方策は，状態 P の選択順については，遷 移元である状態 P のサイズが小さければ，遷移先である δ(P, a) のサイズも小さくなる可 能性が高いと考え，サイズの小さい状態 P を優先的に選択する戦略を考えた．また，文 字 a の選択順については，a∈ Σ である全ての文字 a について δ(P, a) をあらかじめ求め ておいて，その δ(P, a) のサイズが小さくなる文字 a を優先的に選択する戦略を考えた．
4.2
実験
4.2
：
Brzozowski
系アルゴリズムの中間状態数の比較
Brzozowski アルゴリズム及び拡張 Brzozowski アルゴリズムの計算量に違いをもたらす 可能性のある，両アルゴリズムの 2 番目の操作の出力の状態数，すなわち入力の DFA M に対して，Det(Rev(M )) と Atom(Rev(M )) の状態数を実験的に比較した．アルファベッ トサイズ|Σ| = 2 の到達可能な DFA を，各状態数につき 200 個ランダムに生成して用い た比較結果を表 4.1 に示す． ただし，実装には Python 2.7.16 を用い，到達可能な DFA のランダムな生成，反転，及 び決定性化は，形式言語操作モジュール FAdo [9] を用いて実現した．V´azquez らのアル ゴリズムの実装では，Algorithm 1 の選択待ちの状態を保持する変数L を set 型とし，新 たな状態の集合を update 関数でL に追加し，L から pop 関数で取り出されたものを， そのまま選択された状態 P として用いた．また，アルファベット Σ も set 型とし，Σ か ら for 文で取り出されたものを，そのまま選択された文字 a として用いた．すなわち，状 態 P や文字 a の選択順は，Python 本体の上記要素の実装によった．ただし，文字につい ては，実装上は Σ = {0, 1} であり，その選択順は常に 1, 0 の順であった．特に断りがな い限り，本実装を本論文の他の実験でも用いるものとする．表 4.1 より，拡張 Brzozowski アルゴリズムの Atom(Rev(M )) の状態数は，Brzozowski アルゴリズムの Det(Rev(M )) の状態数に比べて，最悪時のみならず平均でも大幅に小 さくなることが確かめられた．また，本実験の限りにおいて，第 3 章の定理 4 で述べた， DFA を反転したものを入力とする場合の，V´azquez らのアルゴリズムの出力の状態数の 最大値を超える反例は確認されなかった．
4.3
実験
4.3
：状態の選択順による出力の状態数の変化
V´azquez らのアルゴリズムで任意性のある状態の選択順による，出力の状態数の違いを 実験的に比較した．状態の選択順による V´azquez らのアルゴリズムの出力の状態数の実験 結果を図 4.2，4.3，4.4 に示す．ただし，図 4.2，4.3 は，入力の NFA M = (Q, Σ, δ, I, F ) の アルファベットサイズ|Σ| を固定して，状態数 |Q| を変化させて，出力 Atom(Rev(M)) = (Q′, Σ, δ′, I′, F′) の状態数|Q′| を調べたものであり，図 4.4 は，入力の NFA M の状態数表 4.1: DFA M を入力とする Det(Rev(M )) と Atom(Rev(M )) の状態数の比較結果 入力 M の Det(Rev(M )) の状態数 Atom(Rev(M )) の状態数 状態数 平均 標準偏差 最大値 最小値 平均 標準偏差 最大値 最小値 2 1.60 0.73 3 1 1.46 0.50 2 1 3 3.31 2.03 7 1 2.56 1.20 4 1 4 6.39 3.63 15 1 4.21 1.65 6 1 5 12.34 6.91 31 1 5.71 1.97 8 1 6 21.33 12.83 63 1 7.67 1.95 10 1 8 54.18 32.75 171 1 11.06 1.78 14 1 10 132.66 100.44 839 11 14.15 1.51 17 8 15 735.90 1170.36 15631 64 21.85 1.96 27 17 20 3093.78 3115.27 21740 315 29.11 2.25 37 24 22 5374.23 7668.27 81970 380 31.58 2.13 38 25 を|Q| = 20 に固定して，アルファベットサイズ |Σ| を変化させて，出力 Atom(Rev(M)) の状態数|Q′| を調べたものである．この出力の状態数は，FAdo を用いて各入力条件に つき，ランダムに生成した 200 個の DFA M に対する，Atom(Rev(M )) の状態数の平均 である．また，各図において，Unspecified とあるのは，実験 4.2 で述べた実装による選 択順の結果であり，Mimimum-state-first は，サイズの小さい状態を優先する選択順の， Maximum-state-first は，大きい状態を優先する選択順のそれぞれの結果である． 各図より，入力の状態数|Q| が大きく，アルファベットサイズ |Σ| が小さいときに，サ イズの小さい状態を優先する選択順が有効といえる結果となった．これは，入力の状態 数|Q| が大きいほど，出力の状態数も大きくなり，Algorithm 1 の L に追加される状態の サイズも幅広くなることから，状態の選択順による影響がより現れたと考えられる．ま た，アルファベットサイズ|Σ| が大きいと，δ(P, a) のサイズも幅広くなることから，状 態の選択順による影響が小さくなったと考えられる．
0 10 20 30 40 50 60 70 80 |Q| 0 20 40 60 80 100 120 |Q'| Maximum-state-first Unspecified Minimum-state-first 図 4.2: 状態の選択順による，V´azquez らのアルゴリズムの出力の状態数の違い（|Σ| = 4）． 0 10 20 30 40 50 60 70 80 |Q| 0 20 40 60 80 100 120 |Q'| Maximum-state-first Unspecified Minimum-state-first 図 4.3: 状態の選択順による，V´azquez らのアルゴリズムの出力の状態数の違い（|Σ| = 16）． 0 5 10 15 20 25 30 alphabet size 0 5 10 15 20 25 30 35 |Q'| Maximum-state-first Unspecified Minimum-state-first 図 4.4: 状態の選択順による，V´azquez らのアルゴリズムの出力の状態数の違い（|Q| = 20）．
