NonDisjointSetsクラス
NonDisjointSets
クラスは、ある集合と交わるような集合の集合(入れ子のfrozensetのようなもの)です。このクラスはDFAの受理状態を作るのに使います。
DFAの受理状態(frozenset型)は前述したように、NFAの受理状態(整数型)を1つでも含んでいるようなDFAの状態(frozenset型)となります。よって、「NFAの受理状態の集合(frozenset型)」のNonDisjointSets
を考えると、NonDisjointSets
に含まれるfrozensetは全てNFAの受理状態(整数型)を1つ以上含んでいますので、このfrozensetはDFAの受理状態となります。
それでは、NonDisjointSets
の実装について説明します。前述したように、NonDisjointSets
は集合の集合です。なので、入れ子のfrozensetでも表現が可能のように思えます。しかし、これは得策ではありません。一つ例を考えてみましょう。{1, 2, ..., 20} の20個からなるNFAの受理状態が{ 1 }とします。この{ 1 }のNonDisjointSets
を考えてみます。例えば、{ 1, 2 } { 1, 3, 4 } { 1, 12, 15, 20 } 等はこのNonDisjointSets
に含まれます。他の要素もあわせて含まれる要素を全て数えると、何個くらいあると思いますか? 1は含まれるので固定で、残りの19個の要素の任意個数の組み合わせとなりますので……答えは2の19乗、524,288個です。このようにNonDisjointSets
は2のベキ乗個の要素を持つ集合であるため、素直にfrozensetの入れ子として実装すると大変なことになってしまいます。これが、第2回のコラムで述べたDFAの状態数が膨らんでしまうと言う問題です。
そこでNonDisjointSets
を、frozensetと同じように振る舞うものとして実装します。そのために、Pythonの強力なダックタイピングの特性を利用します。NonDisjointSets
はfrozensetと継承関係を持ちませんが、代わりにfrozensetと同様な操作を持たせます。ただし、frozensetの持つ操作全てを実装するのは大変なので、ここでは一部の操作だけを実装します。
DFAを動作させるとき、受理状態に対して行う操作は以下だけでした。
def is_accept_state(self): return self.cur_state in self.DFA.accepts
NonDisjointSets
はDFAの受理状態としてしか使いませんので、このin(メンバシップテスト演算子)さえ実現できれば用は足りそうです。inの振る舞いは、特殊メソッドである__contains__
によって実装できます。
結果として、NonDisjointSets
クラスの実装は以下のようになります。
class NonDisjointSets(object): def __init__(self, sub): self.sub = sub def __contains__(self, a_set): return a_set & self.sub
元となる集合を、self.sub
に保存します。このself.sub
と交点を持つ集合であれば、このSubsetIncludingElem
の要素となります。SubsetIncludingElem
のイメージは入れ子のfrozensetですから、その要素もfrozensetです。つまり、in演算子で比較対象になる要素(__contains__
の引数)も、frozenset型となりますので、& 演算子によって積集合を求めて、元となる集合との交点のあるなしを求めています。
部分集合構成法の実装
これで道具は揃いました。実際のこの部分集合構成法を実装し、NFAをDFAに変換してみましょう。DFAの作成に必要なものは、「遷移関数」「開始状態」「受理状態の集合」でした。これら3つを、順番に実装していきます。
以下、元となる NondeterministicFiniteAutomaton
クラスのインスタンスを nfa
とします。
遷移関数
nfa.transition
から、新たなtransition
を定義します。以下のように実装します。
def transition(set_, alpha): ret = set() for elem in set_: ret |= nfa.transition(elem, alpha) return nfa.epsilon_expand( frozenset(ret) )
遷移関数はDFAの要素を引数として取りますが、DFAの要素はNFAの状態の集合でした。つまり、遷移関数にはfrozenset型が渡ってきます。
このfrozenset型の要素はNFAの状態なので、それぞれを nfa.transition
で遷移させることができます。そして、nfa.transition
の戻り値として返ってくる「次に取りうる状態の集合」を、全て和集合として集めた物が DFA上で次に遷移すべき状態となります。frozensetにおいて、和集合は |演算子 で計算できますので、各要素に対して nfa.transition
をした結果を、 |演算子 で和をとっています。
最後に、前述したように空文字列遷移をさせる必要があります。これは既にepsilon_expand
メソッドとして実装済みですので、このメソッドを利用して拡張した状態集合を戻り値とします。
開始状態
これは、NFAの開始状態のみからなる集合です。が、開始状態から空文字列の遷移がある場合は、他の文字による遷移の前にこの遷移を処理しなければなりません。そこで、開始状態もepsilon_expand
メソッドで拡張します。
nfa.epsilon_expand( frozenset([ nfa.start ]) ),
受理状態の集合
前述したように、DFAの状態として表されるNFAで取りうる状態の集合の中に、1つでもNFAの受理状態が含まれていれば、そのDFAの状態は受理状態と言うことになります。
この要件を満たすために、NonDisjointSets
を実装したのでした。nfa.accepts
に対する NonDisjointSets
インスタンスを作成すると、nfa.accepts
の要素を1つ以上含むNFAの状態の集合(DFAの状態)の集合となります。
NonDisjointSets(nfa.accepts)
以上をまとめると、nfa2dfa
の実装は以下のようになります。
def nfa2dfa(nfa): def transition(set_, alpha): ret = set() for elem in set_: ret |= nfa.transition(elem, alpha) return nfa.epsilon_expand( frozenset(ret) ) return DeterministicFiniteAutomaton( transition, nfa.epsilon_expand( frozenset([ nfa.start ]) ), NonDisjointSets(nfa.accepts) )
これで部分集合構成法nfa2dfa
の実装が終わり、正規表現エンジンに必要な道具は全て揃いました。いよいよこれらの道具を組み合わせ、正規表現エンジンを完成させます。