正規表現エンジンを作ろう （2）

NFAとDFAを実装する

NondeterministicFiniteAutomatonクラス

　以上のことを踏まえ、NFAをPythonコードで表すと、以下のように3つのフィールドをもつクラスとして表現出来ます。

NondeterministicFiniteAutomatonクラス

class NondeterministicFiniteAutomaton(object):
    def __init__(self, 
                 transition , # 遷移関数
                 start      , # 開始状態
                 accepts    , # 受理状態の集合
                 ):
        self.transition = transition
        self.start      = start
        self.accepts    = accepts

　このクラスの利用例として、インスタンス化して下記の遷移図のようなNFAオブジェクトを作成してみます。

NFAオブジェクトの例

　この遷移図に該当するNFAを作成するには、以下のような引数を与えます。

NFAオブジェクトのインスタンス化

def transition(state, char):
    if state == 0 and char == u"a": return frozenset([1, 2])
    if state == 1 and char == u"b": return frozenset([2])
    if state == 2 and char == u"" : return frozenset([0])
    return frozenset([])

nfa = NondeterministicFiniteAutomaton(
    transition,
    0,
    frozenset([2])
    )

　では、引数について見ていきましょう。

　最初の引数として渡しているtransitionは「遷移関数」で、直前のdef文によって定義されたfunction型です。この遷移関数が遷移図の矢印を表せていることを確認してみます。例えば、状態が0の時に'a'が入力された場合、遷移図の矢印を見ると状態1か2に遷移すればいいことがわかります。そこで、試しに transition(0, 'a') を計算してみると、戻り値はfrozenset([1, 2])となります。これは、先ほどみた遷移図の矢印と一致しています。

　2つ目の引数は「開始状態」で、このNFAは状態0から始まることを表しています。遷移図のスタート地点も状態0であり、一致しています。

　3つ目の引数は「受理状態の集合」で、このNFAでは2だけです。遷移図中の二重丸が受理状態ですから、これも図と一致しています。

NFAの別の表現方法

　NFAは状態を示す複数個の丸と、それらの状態間の状態遷移を表す複数個の矢印を利用して表現することができます。実装に当たって、この図を忠実にモデリングすることも可能です。つまり、状態（丸）一つ一つをオブジェクトとし、矢印をオブジェクト間のリンクとしてモデリングするという実装方針もありえます。

　ただしこの実装を行うと、次回以降に説明するNFAからDFAへの変換で、モデル内に存在するオブジェクト数が膨大になってしまいます。筆者が試したところ、「(p(erl|ython|hp)|ruby)」程度の正規表現でもDFAになった時点で数十万個の状態が発生し、メモリが不足して動作しませんでした。そのためこのような実装をする場合には、NFAをDFAに変換する部分で最適化を施し、DFAの状態数を最小に保てるように工夫する必要が出てきます。

　また、NFAエンジンでは、NFAを「遷移矢印を総当たりで辿るバイトコード」として表現します。これに関しては、連載の最後で簡単に説明する予定です。

練習: このNFAが受理する文字列

　頭の体操代わりに、このNFAで受理される文字列を考えてみましょう。最初に答えを言うと、このNFAが受理する文字列は a, ab, aaaba, aabaaaabaa ... のように、"aの列の合間にbがあるもの"となります。逆に、b, aabb, aaabbbaaa ... のような文字列は受理されません。

　例えば、aba が受理される時は、以下のような動きとなります。図と併せてみるとわかりやすいとおもいます。なお、 'aba' は 'a' + 'b' + '' + 'a' と見なせることに注意して下さい。

1. 最初は状態0
2. 'a' を入力すると、transition(0, 'a') がfrozenset([1,2])なので、状態1を選んで遷移
3. 'b' を入力すると、transition(1, 'b') がfrozenset([2])なので、状態2
4. ここで、空文字('')の読み込み をすると、transition(2, '') がfrozenset([0])なので、状態0
5. 'a' を入力すると、transition(0, 'a') がfrozenset([1,2])なので、状態2を選んで遷移（受理状態）

　NFAでのシミュレートは、非決定性によって色んな選択肢があるためにややこしくなります。考え方に慣れておくため、他の文字列も実際に計算して試してみるとよいでしょう。