一泊二日コード漬け

terapyonさんの主催している開発合宿に参加させてもらいました。

初めてこういうのに参加しましたが、はかどり方が半端じゃないです。一人で家で開発作業をやってると、30分〜1時間くらい開発した辺りで飽きが来て遊びに出たりしてまうことが多いのですが、周囲で作業をやってる人がいるとそうもいかなくなります。仕事でやってるんじゃなく、みんな好きで集まってやってるってのがうまく前向きな雰囲気を作っていて、相乗効果で自分もやる気になりました。こんなに開発に没頭したのは久々。

今回はオートマトンの本で得た知識を使って、pythonでDFAによる正規表現エンジンを作るつもりでした。しかし、NFAからDFAを構築するとこで挫折。数学的な証明で利用するDFAの構築方法では、NFAの状態集合のベキ集合をDFAの状態集合とします。例えば状態が20個のNFAに対して真面目にDFAを構築すると、1,048,576個の状態を持つDFAになるんですよね・・・実装しようとするまで気がつかなかったorz 初期状態と遷移関数を睨めっこして、必要な状態だけでDFAを構成する方法を考えたんですが、スマートな方法が思いつかず*1、結局NFAのまま評価しました。動いたからまあよしとしますか。

>>> import dfareg
>>> dfareg.strict_match("(p(ython|erl|hp)|ruby)*", "pythonperl")
True
>>> dfareg.strict_match("(p(ython|erl|hp)|ruby)*", "rubyphp")
True
>>> dfareg.strict_match("(p(ython|erl|hp)|ruby)*", "java")
False