2007-02-21から1日間の記事一覧

dfa-0.02 DFA 状態数の最小化対応版(まだ NFA 経由)

昨日の「dfa-0.01 正規表現から DFA へ(NFA 経由版)」は、動くのですが、問題がありました。正規表現によっては、DFA の状態数が膨らんでしまうのです。 例えば、xy で終わるけど、途中には xy が現れない文字列にマッチする正規表現 /(?:(?!xy).)*xy/ を開…