Atzy->getLog()

■[正規表現] 「電話番号、郵便番号にマッチする真の正規表現」の作り方

電話番号、郵便番号にマッチする真の正規表現 - にぽたん研究所

これ、実用には全くならない(使ってはいけない)けど面白いなあ。

この手の正規表現をどうやって生成するのかということですが、(自称)正規表現専門家の私が推測してみます。(ただの推測なので、正解かどうかは保証しません。)

簡単かつ等価な正規表現

結局、狂ったような正規表現に見えますが、本当は、次のような正規表現でも全く等価なものを正しく受理するのです。

(1010001|1010002|...) ←正しい郵便番号の並びが10万以上続く

これは、郵便番号データさえあれば、誰でも作れる正規表現です。しかし、これをブログやらスライドに載せても「はいはい。楽しいですか？」といわれるだけです。これを難しげな正規表現に変換しないとネタになりません。

正規表現をコンパイル(NFA生成)

この正規表現をコンパイルします。つまり、中身を解釈してNFAを作ります。これは正規表現ライブラリを実装する人なら誰でもできます。

NFA→DFA変換

そのようにして作られたNFAを今度はDFAに変換します。これもアルゴリズムの教科書に載っている話で、正規表現ライブラリではよく実装されます。結局NFAの複数の状態の組をDFAの一状態にするので状態数は一般に多くなります。ただ、今回の場合は、結局状態数はあまり変わらないんじゃないですかね。

ある入力によって遷移をしていった時に、「NFAでは状態Aにも状態Bにも存在することが可能」だとしたら、この状態Aと状態Bの組を新たなDFAの状態とする感じですね。なお、DFAは一意には決まりませんので、何も考えずにアルゴリズムを実装したものよりもよりよい(小さい)DFAができることがあります。

DFA→正規表現変換

作られたDFAを今度は正規表現に変換します。

実際、私はやったことはありませんが、教科書には書いてありましたね。

 [状態A] ─┬─(1,2,3) ─[状態B] ─┬─(9,0)──[状態C](終了状態)
 　　　　　│　　　　　　　　　　　└─(3)──[状態D]─(1,2)─[状態E](終了状態)
 　　　　　└─(4,5)───[状態F](終了状態)

こんな感じだとすると、状態を木としてたどりながらそのまま正規表現に展開できます*1。つまり、([1-3]([90]|3[12]))|[45] のように変換します。

一般に、複数の経路で同じ状態に達したとしても無視して展開するとマジキチに長い正規表現になりますが、今回のような例、つまり「(1010001|1010002|...)」のようなものから作った場合では、そもそも同じ状態にたどり着くことはないでしょうから、長くなることの本質ではありません。

そう考えると、誰でも正規表現の生成はできる気がします…よね。