はじめに
こんにちは。hirataraです。
前回までの連載で、正規表現からNFAを構築する部分までを作成しました。今回は、NFAをDFAに変換する部分集合構成法を解説し、今まで作った部品を組み合わせて正規表現エンジンを完成させます。
対象読者
- 正規表現をもっと知りたい方
- 情報科学分野に興味がある方
- 正規表現エンジンを実装する必要がある方
部分集合構成法
NFAをDFAに変換するには、部分集合構成法（subset construction）と呼ばれる方法を利用します。
第1回で説明した通り、NFAは1つの文字の入力によって一意に状態が決まらないのが特徴でした。'a'を入力すると、1になるかもしれないし、2になるかもしれません。そして、NFAのシミュレート方法には、バックトラックを利用する深さ優先の方法と、もう一つ、幅優先の方法があることも紹介しました。幅優先の動作では、入力による遷移の全ての可能性を集合として保持しながら文字列の入力を処理します。以前利用した、以下の遷移図を見ながら考えてみましょう。
まず、このNFAの初期状態は 0 ですので、最初にとりうる状態の集合は{ 0 } となります。そしてこの状態で'a'が入力すると、次にとりうる状態は{0, 1, 2}です（εは空文字なので，入力がなくても状態2から状態0へ遷移します）。さらに見て行くと、'b'が入力されると{ 0, 2 }、次に'a'が入力されると{0, 1, 2} ... と言った感じで状態の集合がどんどん遷移していくのが分かります。
この幅優先の動作を注意深く観測してみて分かることは、入力に対して次に遷移しうる「状態」は複数ありそうですが、「取りうる状態の集合」は一意に定まっていると言うことです。例えば最初に'a'を入力する部分を見ると、次に遷移する状態は0になるかも1になるかも2になるかもしれず定まりませんが、取りうる状態の集合は{0,1,2}と一つに定まります。この、一つに定まる、と言うのがDFAの性質とうまく合致しています。
このような考え方を元にして、NFAの「取りうる状態の集合」をDFAの「状態」としてNFAからDFAを作成する方法を、部分集合構成法（subset construction）と呼びます。
部分集合構成法でDFAを構築する
それでは、実際にNFAからDFAを作ってみましょう。部分集合構成法によってDFAを構成する場合、DFAの5つの要素は、元となるNFAを使って以下のように構築されます。
| DFAの要素 | 構築方法 |
| 状態の集合 | NFAの「状態の集合」のベキ集合 |
| 文字の集合 | NFAの「文字の集合」 |
| 遷移関数 | NFAの「遷移関数」から作成（後述） |
| 開始状態 | NFAの「開始状態」と空文字（ε）だけで遷移できるNFAの「状態」からなる、このDFAの「状態」 |
| 受理状態の集合 | NFAの「受理状態」を1つ以上含む、このDFAの「状態」の集合 |
先ほどのNFAからこの方法によってDFAを構成すると、図のようになります。以降、この図を見ながら説明を読むとわかりやすいと思います。
DFAの「状態」
状態の集合の構築方法の中で、ベキ集合と言う言葉が出ていますが、これは数学の集合論の概念です。念のため簡単に説明します。
「ある集合のベキ集合」とは、その集合の部分集合の集合のことです。例えば、{1, 2, 3} のベキ集合は {{}, {1}, {2}, {3}, {1, 2}, {2, 3}, {3, 1}, {1, 2, 3}} となります。Pythonの世界で言えば、frozensetを要素とするfrozenset、つまり、入れ子にしたfrozensetと言うことになります。
もしベキ集合による定義がよく分からなければ、単純に「DFAの状態は、NFAの状態の集合」と考えると分かりやすいです。つまり、今までNFAでは、1や2などの整数値を状態と呼んでいましたが、DFAの世界では代わりに、frozenset([1, 2])やfrozenset([3, 4, 5])のようなfrozenset型を状態と呼ぶと言うことです。状態遷移図の世界で言えば、NFAでは丸の中に1や2を書いていたのが、DFAではその代わりに1,2や3,4,5のように複数の数字を書くと言うことに該当します。
こんな風にDFAの「状態の集合」を定めることで、NFA上で状態2か状態4を取りうる、と言うことをDFA上で状態{2, 4}である、と言い換えることができるようになります。また、NFA上で取りうる状態がないことを、DFA上では状態{}（空集合:要素の入ってない集合）で表すことができます。
DFAの「遷移関数」
次に、遷移関数の構築について解説します。第2回で説明した通り、DFAとNFAでは遷移関数の引数と戻り値が微妙に違います。加えて先述のとおり、DFAとNFAでは状態を表す型が整数型とfrozenset型と言うように異なっています。遷移関数の構築において、この2つの違いを十分に注意する必要があります。以下にまとめておきますので、参考にして下さい。
| 引数 | 戻り値 | |
| NFA | 今の状態（整数型）, 文字 or 空文字（ε） | 次の状態の集合（frozenset型） |
| DFA | 今の状態（frozenset型）, 文字 | 次の状態（frozenset型） |
それでは、DFAの遷移関数がどうあるべきか考えてみましょう。DFA上の「状態」は、NFA上での「取りうる状態の集合」でした。なので、DFA上の「状態（frozenset型）」に含まれるNFA上のそれぞれの「状態（整数型）」をNFAの遷移関数で移し、それらを全部集めたものに該当するDFA上の「状態（frozenset型）」が、DFAの遷移関数の戻り値となりそうです。
もっと具体的に、DFAの遷移関数の立場で考えてみましょう。DFAの遷移関数には、frozensetが渡ってきますが、この中にはNFAの状態である整数型が入ってます。NFAの状態遷移関数は整数型を引数にしますので、これらの整数型を一つずつ渡すことができます。そして、NFAの状態遷移関数からは次にとりうる整数型の状態のfrozensetが戻ってきます。これらを和集合として集めたfrozensetを、DFAの遷移関数の戻り値とすれば、先の要求を満たせます。
ただし、これだけではε（イプシロン：空文字列""のこと）の遷移を表現できません。εは入力がなくても進む遷移ですので、これを表現するためには1文字の入力で複数回遷移関数を呼び出す必要があります。具体的には、まず入力された1文字で遷移関数を呼んだ後、次に空文字列（""）で遷移関数を呼びます。空文字列による遷移は何度も続く可能性があるので、遷移できなくなるまで再帰的に遷移関数を呼ばなければなりません。
DFA変換のための道具を実装する
方針が大体見えてきましたので、DFA変換に使うための道具を作成します。以下の2つを作っておきます。
epsilon_expandメソッド（遷移関数で利用）NonDisjointSetsクラス（受理状態で利用）
epsilon_expandメソッド
epsilon_expandメソッドはNondeterministicFiniteAutomatonクラスのメソッドで、状態集合から空文字列εによる遷移を繰り返して到達できる範囲の集合に広げるメソッドです。前述した通り、「遷移関数」の作成に必要な処理です。また、「開始状態」の作成にも利用します。
def epsilon_expand(self, set_):
# 空文字を辿るべき状態を集めたキュー
que = set( set_ )
# 辿り終わった状態
done = set()
while que:
# キューから取り出す
stat = que.pop()
# 空文字によって辿れる遷移を辿る
nexts = self.transition(stat, "")
# この状態は辿り終わったので、保存
done.add(stat)
# 辿って出て来た状態を、さらに空文字で辿るのに、キューに居れる
for next_stat in nexts:
# 辿り終わってない要素だけ
if not next_stat in done: que.add(next_stat)
return frozenset( done )
このメソッドは、NFAの状態の集合を引数に取ります。そして、そこから空文字で辿れる範囲にある全ての状態を集めた集合を戻り値として返します。引数も戻り値も「NFAの状態の集合」なので、整数型を含むfrozenset型となります。
実装を簡単に説明します。最初に、処理前の状態を集めるqueと処理済の状態を集めるdoneと言う2つのset型を用意してます。queに入っている状態に対し、NFAの遷移関数（self.transition）によって空文字遷移を行います。そして、遷移後の状態に対しても再帰的に空文字を辿らなければならないので、この新たな状態を全て待ち行列であるqueに放り込みます。
ただし、ここで処理済の状態をqueに入れてしまうとqueが一向に減らず無限ループしてしまいます。そこで、処理済の状態が再びqueに入ることのないように、doneで制御しています。空文字列遷移処理が終わった状態はdoneに入れ、doneに入っている物を再びqueに入ることがないようにします。
