難しい故事来歴はおいておくものとする。

とりあえず、入力文字列が正規表現にマッチするか否かを判断するためには、正規表現を元に状態遷移図を作って、入力文字列がその状態遷移図に受理されるか否かを判断してやればいい。

つまり、下記のような正規表現が与えられた場合、

a(b|c)d

次のような状態遷移図を作ってやって、

入力文字列を使って、上記の状態遷移図を辿っていって、最後にきっちりゴールにたどり着くか否かを判断してやればいい。

状態遷移図中の、丸に「i」が書いてある奴がスタートで、二重丸に「f」が書いてある奴がゴールである。そして、矢印とその上に書いてある文字は、入力文字列中の文字とそれに対応する遷移先を示している。

つまり、誰だか知らないが主人公がスタート地点にいて、入力文字列の一文字目が「a」だったなら二つ目の丸に進むことができる、ということを表している。

例えば、入力文字列が「abd」であれば、名無しの主人公は下記のようなコースを進んでいくことになる。

もしここで、我らが名無しの主人公が、入力文字列の最後の文字を使って遷移したときに、ちょうど状態遷移図のゴールにたどり着くことができれば、「この入力文字列は状態遷移図に受理された」と言う。

してみると、状態遷移図というのは、お役所のようなものなのだろうか？　まぁそれはどうでもいいか。

では次に、主人公がきっちりゴールにたどり着けなかった場合について考えてみる。

例えば、入力文字列が「abc」だった場合は、主人公はゴールにたどり着くことができない。何せ「b」の次は「d」でなければ次へ進めないのだから。

また、入力文字列が「abdd」だとしても、主人公はゴールにたどり着けないものと考える。主人公は、三文字目の「d」でゴールに到着するのだが、しかし、まだ文字「d」が余っており、その文字をなんとしても使い切ってしまわなければならないのだ。

このように、主人公が入力文字列の最後の文字できっちりゴールにたどり着くことができない事を「入力文字列は状態遷移図に受理されなかった」と言うらしい。まぁ、否定形にしただけなんだが。

ε遷移

状態遷移図中には、空遷移（ε：イプシロンと読むらしい）という嫌なものがある。

これは、入力文字列を消費せずに進むことができる遷移を表している。つまり、下記のような状態遷移図が与えられた場合、

入力文字列としては、「abd」「acd」以外にも、「ad」という文字列を受理することができる、ということになる。

また上記の状態遷移図では、ある一つの状態から遷移可能な方向が複数になりうるという性質を持っている。つまり、入力文字列が「abd」で、我らが主人公が下記の赤丸の部分にいたとした場合、遷移可能な方向は「b」と「ε」の二つになりうるということだ。

この例では、どちらを辿っていっても同じ所に行くのだからどうでも良いと思うかも知れないが、しかしそうはいかない。入力文字列の「b」を消費するか否かという違いがあるのだ。

だから、もし主人公が「ε」の方を通って前に進んだとしたら、次は「d」でなければ前に進めないため、ゴールにはたどり着けないことになるのだ。つまり、この場合の正解のルートは「b」の方向ということになる。

もし、コンピューターで入力文字列が受理されるか否か判断させようとした場合は、正解のルートがどれなのか判らないので、可能性のあるルートは全て虱潰しに試してみる、という処理を行うことになる。そのため、場合によっては非常に時間がかかってしまう場合があり得る。

なお、上記のように、遷移先が複数あり得る状態遷移図のことを、非決定性オートマトン（NFA：Nondeterministic Finite Automaton）と言うらしい。なお、オートマトンの日本語訳は、自動機械であって、自動羊肉ではないらしい。

正規表現からNFAを作成する

正規表現として、以下の三つのパターンについて考えてみる。

R|S

RS

R*

「R」と「S」は、正規表現の一部分を表している。

「R|S」は、いわゆるorであって、RかSのどちらかであればよい状況を示している。

「RS」は、Rの後にSが続く状況を示している。

「R*」は、Rが0回以上繰り返すことを示している。

実用的な正規表現では、もっと複雑な機能を提供していることが多いのだが、それらは上記の応用として考えることができる。

また、初めから難しいのを考えても、俺の知能では追いついていけなくなるから、簡単なものに限定して考えることにする。（というか、大概の解説本では、上記のパターンで説明していることが多いのだ。）

R|S

「R|S」のパターンについて考えてみる。

「R|S」は、RまたはSということなのだから、状態遷移図にした場合は、二つの経路があるような図になる。

例えば、Rの正規表現が「abc」で、Sの正規表現が「xy」なら、RとSのそれぞれの状態遷移図は下記のようになり、

「R|S」、つまり「abc|xy」は、下記のような状態遷移図となる。

RS

「RS」は「R」の後に「S」が続くのだから、下記のようになる。

例えば、「R」が「abc」で、「S」が「xy」ならば、下記のようになる。

R*

「R*」は、「R」が0回以上繰り返すという意味だ。だからそれを状態遷移図で表すと、下記のようになる。

εが多数あってうざいが、こういうものなのだから仕方がない。

上記の理論だけあれば、一応状態遷移図を作ることができるし、その状態遷移図を元にマッチング処理を実装することも可能である。現に、「主筆」が使用している正規表現ライブラリではNFAを使用している。

NFAからDFAを作成する

決定性有限オートマトン（DFA:Deterministic Finite Automaton）とは、NFAとは違い、ε遷移が無く、一つの状態から同じ記号で異なった複数の状態に遷移することがない状態遷移図のことである。

得られた状態遷移図を元にパターンマッチングを行う際、NFAでは再帰的に処理を行わなければならないのだが、DFAではその必要が無くなるため、何かと便利なことが多い。

そのため、一般的な正規表現ライブラリの実装ではDFAを用いる事が多い。

正規表現からDFAを直接作る方法は、俺は知らない。そういうやり方があるのかどうかすらも知らない。ただ、DFAはNFAを元に、機械的に変換することで作成することができるらしい。

簡単に書くと、下記のようなアルゴリズムになる。

ある状態からεで遷移できる状態を、全部まとめて一つの状態にしてしまう。

1で作った状態から、ある一つの記号で遷移可能な状態と、そこから更にεで遷移可能な状態をまとめて、一つの状態にする。また、1で作った状態から、2で作った状態への遷移は、2の状態を作成するときに使用した「ある一つの記号」を用いる。

1と2を変化がなくなるまで繰り返す。

例として、「a(bc)*d」という正規表現を、DFAに変換してみる。

上記の正規表現をNFAで記述すると、下記のようになる。

まずは、初期状態からεで遷移可能な全ての状態をまとめて、一つの初期状態とする。しかし、上記のNFAでは、初期状態からはε遷移は出ていないため、特にすることはなく、下記のようになる。

初期状態から記号aにより遷移可能な状態（つまり状態1）と、そこからεで遷移可能な全ての状態をまとめて、一つの状態を作成する。

状態1からεで遷移可能な状態には状態2と状態5がある。

そのため、状態1と状態2と状態5をまとめて、単独の状態1・2・5とする。だから、DFAは下記のようになる。

状態1と状態2と状態5から出ている（ε以外の）遷移には、記号bと記号dがある。そのため、状態1・2・5から出る遷移も、記号bと記号dとなる。

今度は、状態1・2・5から記号bで遷移可能な状態と、更にそこからεで遷移できる全ての状態をまとめた一つの状態を作成する。

状態1・2・5から記号bで遷移可能な状態は、状態3しかない。また、状態3からはε遷移はできないため、DFAは下記のようになる。

状態3から出ている遷移は、記号cだけである。

同様に、状態1・2・5から記号dで遷移可能な状態と、更にそこからεで遷移できる全ての状態をまとめた一つの状態を作成する。

状態1・2・5から記号dで遷移可能な状態は最終状態だけであり、最終状態からはε遷移は出ていない。そのため、DFAは下記のようになる。

状態1・2・5からの遷移は、これで完成である。そのため、今度は状態3からの遷移について考えてみる。

状態3から記号cで遷移可能な状態は状態4である。また、状態4からεで遷移可能な状態には、状態2と状態5がある。そのため、状態2と状態4と状態5をまとめて、状態2・4・5を作成する。

状態2と状態4と状態5からは、記号bで状態3へ、記号dで最終状態へ遷移している。そのため、下記のようになるところではあるが、

しかし、状態3と最終状態はすでに書きかけのDFA中に存在するため、それそれの遷移をすでに存在している状態に結びつけて、下記のようにする。

これ以上はいじるところがないので、上記の状態でDFAは完成となる。

DFAの簡略化

上記のアルゴリズムで作成したDFAには、たまに無駄が生じる場合がある。だから、作成したDFAの簡略化を行う必要がある。

もっとも、多少無駄があっても問題ないというのであれば、このステップは省略できるのだろうが。

簡略化できる場合というのは、二つの状態を一つにくっつけることができる場合の事を表している。つまり、図の上では二つに分かれてはいるものの、実は本質的には全く同じで、二つに分かれている必要がない、という場合があり得るのだ。

では、どういうときに一つの状態にまとめることができるのか。簡単に書けば「記号と遷移先の組み合わせが全く同じ状態」は一つにまとめることができる。

例えば、「a(a|b)*b」という正規表現について考えてみる。

これをNFAにすると、下記のようになる。

そして、これを上記のアルゴリズムに従ってDFAに変換すると、下記のようになる。

この図を眺めていても何がなんだか判らないから、状態遷移表という表を作ってみる。

状態遷移先

記号a 記号b

i 1・2・4 　

1・2・4 2・3・4 2・3・4・f

2・3・4 2・3・4 2・3・4・f

2・3・4・f 2・3・4 2・3・4・f

上記の表を眺めていると、状態1・2・4と、状態2・3・4は本質的に同じであることが判る。つまり、状態1・2・4と状態2・3・4は、どちらも記号aで状態2・3・4に遷移し、記号bで状態2・3・4・fへ遷移しているので、区別する必要がないのだ。

なお、状態2・3・4・fも同じように見えるかも知れないが、これはfを含む最終状態であるため、まとめてしまうわけにはいかない。つまり、最終状態か否かという違いがあるのでまとめられない。

これを元に状態遷移図を書き直すと、下記のようになる。

上記のDFAの状態数は、これで最小である。これ以上は簡略化できない。

ただし、上記の処理だけでは完全に冗長性を排除することができない場合もあるらしい。しかし、これ以上は俺の手に追いかねるから省略する。

補足

一応上記の処理を実装して、その他諸々の細かい処理を追加してやれば、正規表現でパターンマッチングを行うプログラムや、あるいはlexの偽物のようなものを作ることも可能である。

ただ、まぁ、できれば既存のものを使用する方が良いのは、言うまでもないことだがなぁ。