NFAとDFA
正規表現は強力で便利ですが、この機能を直接プログラムで実装するとなると結構大変です。そこで、正規表現と等価であり、計算機で実現しやすい別の概念を導入します。それが、「オートマトン」と呼ばれる仮想的な機械です。
有限オートマトン
数学的な正規表現は、NFAやDFAと呼ばれるオートマトンと等価であることが知られています。「FA」とは、Finite Automaton の略で、日本語では有限オートマトンや有限状態機械と言います。
有限オートマトンは、文字列を入力すると真偽値を出力する機械です。内部に有限個の状態を持っており、1文字入力するごとにその状態を変化させます。そして、最後の文字を入力した時の状態が「受理状態」と呼ばれる状態かどうかで、出力が決定されます。
NFAやDFAを表すには、以下にあるような状態遷移図と呼ばれる図を利用します。円は、状態を表しており、矢印は文字の入力によって状態がどのように変化するかを示します。最初の矢印が指している円が開始状態で、有限オートマトンはこの円の状態からスタートします。二重丸で書かれている円は受理状態であり、最後の文字が入力された後に受理状態に留まっていれば、真を出力します。
この図において、εは空文字('')を表します。空文字とはその名の通り空っぽの文字であり、他の文字列と繋げても文字列を変化させません。例えば、'a'+''+'b'は'ab'となります。
では、遷移図を見てみましょう。この例では、'a'→'c'→'b'→εと辿ると、5に辿り着くことができます。5は二重丸の円ですので、この入力、つまり、文字列"acb"はこのNFAに受理され、真となります。1のときに右の矢印に進んでしまうと5には辿り着けませんが、うまく矢印を選んだ時に二重丸に辿り着けさえすれば受理されると見なします。また、途中で二重丸の4を通過しますが、通過するだけでは真ではなく、あくまでゴールが二重丸である必要があります。
このNFAでは同様に"abcad"や"acbcd"も受理されます。練習のため、本当に受理されるか試してみて下さい。
NFAとDFAの違い
NFAのNは、Nondeterministic の略で、「非決定性」を意味します。「非決定性」とは、入力によって状態が一意に決まらないことを意味します。状態遷移図で言えば、一つの円から同じ文字によって複数の円に矢印が引かれている状態を表します。入力によって状態1に行くかもしれないし状態2に行くかもしれないと言うことは、NFAの動作をシミュレートする時は考えうる全ての状態遷移を実行する必要があることを意味します。
NFAではまた、空文字列（ε:イプシロン、または '' で表します）での状態遷移を許可します。これは、文字列から1文字読み込む時に、空文字を読み込んだことにして文字を読み込まずに状態を移してもいいと言う意味です。このルールに従うと、例えば "abc" と言う文字列は、 'a'、'b'、'c' と入力してもいいし、 'a'、 ''、 'b'、 ''、 'c'、 '' と入力しても構わないことになります。さらに複雑に、''、''、'a'、''、''、''、'b'、''、''、'c' 等としても一向に構いません。
これらの「非決定性」は、 NFA の実装を複雑なものにします。
対する DFA は、非決定性がない有限オートマトンです。 DFA の D は、 deterministic の略で、「決定性」を意味します。NFAとは違い、入力文字によって遷移する先の状態は"ただ一つ"となることが保証されます。この"ただ一つ"と言うのは、遷移先が0個であることも許していないと言うことに注意して下さい。DFAでは全ての入力文字に対して必ず矢印が一つのみ存在します。一文字で複数の状態へ矢印が向いていることも、逆にその文字に該当する矢印がないと言うこともありません。
また、DFAでは空文字列(ε)での遷移も許されていません。このような制約により、DFAではある一時期にとりうる状態は1つしかありません。よって動作をシミュレートするには、現在の状態を1つだけ保持していれば十分ということになるので，DFAのシミュレーションは非常に簡単です。
ただし、DFAの状態遷移図はNFAよりも制約が多いため考えるのが大変です。全ての文字に対して矢印が必要と言うことは、アルファベットが26文字あれば全ての状態から26個の矢印を書かねばならないと言うことです。さらに入力がUnicode文字になってしまうと……もう手に負えませんね。
正規表現とNFAとDFAの等価性
正規表現とNFAは等価であり、互いに変換が可能です。
では、NFAとDFAはどうでしょう？ NFAとDFAを比べると、DFAの方が制約が厳しく、表現力も低いように感じます。しかし、実はこの2つも等価であり、互いに変換が可能です。
今回の正規表現エンジンの作成では、これらの性質を利用します。まず、正規表現をより表現力が高いNFAで作成します。そしてこのNFAを、シミュレートが簡単なDFAに変換してから実行します。最終的にDFAに変換するため、今回作成するような方式の正規表現エンジンは、「DFAエンジン」と呼ばれます。
NFAエンジンとDFAエンジン
現在プログラミング言語で利用される正規表現エンジンの実装には、DFAエンジンと、もう一つ、NFAエンジンと呼ばれるものが存在します。主流となっているのは、後者のNFAエンジンの方です。
NFAは先ほど説明したように非決定性を持っていますので、複数パターンのある状態遷移の全てをシミュレートできるような作りにする必要があります。この、状態遷移の枝分かれを実現する方法として、以下の2つのアプローチが考えられます。
| 種類 | 説明 |
| 幅優先 | 選択しうる状態を集合とし、全ての可能性を保持しつつマッチするまで広げて行く |
| 深さ優先 | 選択肢を適当に選んで失敗するまで潜り、失敗したら戻って別の選択肢をやり直す |
NFAエンジンが利用しているのは深さ優先の探索方法で、失敗して戻って試行錯誤を繰り返すこの方式を「バックトラック」と言います。バックトラックでは、現在探索中のパスだけに着目した時、選んだ矢印も辿って来た状態もただ一つに定まります。そのため、マッチングの動作を理解しやすく、拡張も比較的作りやすいのが特徴です。この特徴を生かし、NFAエンジンでは後方参照のようなDFAエンジンでは実現しにくい（言い換えると、数学的定義を超えた）拡張が多く取り込まれています。
ただし、NFAエンジンでは失敗する度に文字列の前方へ戻って処理をやり直すため、文字列の同じ部分に何度もマッチを繰り返すことになります。そのため、マッチ時の選択肢の選ばれ方によっては動作が遅くなってしまうと言う特性も持っています。
一方のDFAエンジンは、先ほど紹介した２パターンのうちの幅優先に相当する動作をするため、後方参照のような拡張を行うのは難しくなっています。その代わり、DFAエンジンは文字列を順番に処理し、巻き戻ると言ったことがないため、一定の速度でマッチが可能です。DFAエンジンが解釈できる正規表現は、数学的な定義と同等の場合がほとんどです。
今回の連載では、数学的な定義と同等の正規表現を理解するDFAエンジンを実装します。NFAエンジンのバックトラッキングや後方参照などに関しては全く実装しませんが、連載の最後に少しだけ原理を解説する予定です。
まとめ
今回は、以下の内容を説明しました。
- 正規表現の使い方のおさらい
- 正規表現の数学的な定義
- 正規表現とNFAとDFAの等価性
- NFAエンジンとDFAエンジン
次回以降、DFAエンジンの実装を進めていきます。
参考資料
- 『計算理論の基礎』Michael Sipser 著、渡辺治・太田和夫 訳、共立出版、2000年4月
- 『詳説 正規表現 第3版』Jeffrey E. F. Friedl 著、株式会社ロングテール・長尾高弘 訳、オライリージャパン、2008年4月
- Russ Cox『Regular Expression Matching Can Be Simple And Fast』
