0

たとえば、正規表現は、 、、...go*dなどの文字列に一致するパターンです。gdgodgood

そして、その DFA が 3 ステート マシンのようになることは容易に想像できます。

与えられた文などのパターン検索に使用するとxxxxgodxxxxgoodxxx、 のDFAがgo*dうまくいかないようです。この 3 ステート DFA では、文字さえx定義されていません。

ここでは、追加の「リセット」状態を持つ 4 状態の DFA が機能する可能性があると想像できます。つまり、未定義の文字に遭遇すると、この「リセット」状態に入ります。

問題は、パターン検索ツールが次のような正規表現を使用して検索の目的をどのように達成するgo*dかです。

4

1 に答える 1

0

自明な 3 状態マッチャーが与えられた場合

|start|---/g/---+->|S1|-->-+---/d/--->|accept|
                |          |
                +--<-/o/-<-+

リセット状態は必要ありませんが、 でラベル付けされた開始状態でのキャッチオール再帰遷移は必要ありません[^g]。dfa の定義に厳密に従うと、|Σ|-1それぞれに 以外の 1 つのアルファベット文字でラベル付けされた遷移が必要になりgます。同様に、ラベル付けされた からS1へ、およびstartラベル付けされた からそれ自体への遷移は、パターンの可能なインスタンス化の接頭辞に遭遇した後、適切な「リセット」を保証します。状態を同様に拡張すると、重複しないパターンのインスタンス化 (すべてこの特定のパターンのインスタンス化) をすべてキャッチできます。[^g]S1gaccept

もちろん、これはすぐにこのおもちゃの例よりもはるかに複雑になるため、通常は標準の regex->nfa->dfa 構造が使用されます。

別の戦略は、元の dfa を拡張せずに取得し、start状態を離れるたびにサブプロセスを生成することです。サブプロセスは、その親と同じ dfa を適用し、遷移を開始状態から発火させた文字で始まる特定の文に適用します。

于 2013-03-27T19:12:43.460 に答える