パターン '.*A...' を NFA に映しとったのが左図のオートマトンである。 これと同等な DFA を構成しようとすると、 これが実は右図のように複雑なものになってしまう。 古典的な実装の egrep が

regular expression too long
といって実行をあきらめてしまうのは、 構成しようとした DFA が複雑過ぎて、 ある一定の記憶域に納まらなかったことを意味している。

page10

Prev 9.(正規表現の)パターンマッチの戦略 Next 11.NFA(非決定性)のままの方法の問題点 contents 目次