たとえば、正規表現は、 、、...go*d
などの文字列に一致するパターンです。gd
god
good
そして、その DFA が 3 ステート マシンのようになることは容易に想像できます。
与えられた文などのパターン検索に使用するとxxxxgodxxxxgoodxxx
、 のDFAがgo*d
うまくいかないようです。この 3 ステート DFA では、文字さえx
定義されていません。
ここでは、追加の「リセット」状態を持つ 4 状態の DFA が機能する可能性があると想像できます。つまり、未定義の文字に遭遇すると、この「リセット」状態に入ります。
問題は、パターン検索ツールが次のような正規表現を使用して検索の目的をどのように達成するgo*d
かです。