例如正則表達式go*d是一個模式將匹配字符串喜歡gd，god，good ...用於模式搜索的DFA是什麼？
你能想象它的DFA會像一個三態機。
當它用於模式搜索時，例如，給定句子xxxxgodxxxxgoodxxx，go*d的DFA似乎不起作用。即使在此3態DFA中，字符x也未定義。
我們可以想象一個具有額外「重置」狀態的4狀態DFA可能在這裏工作。也就是說，當遇到未定義的字符時，進入該「重置」狀態。
問題是模式搜索工具如何用go*d這樣的正則表達式實現搜索目的？
給出的瑣碎三態匹配
|start|---/g/---+->|S1|-->-+---/d/--->|accept|
| |
+--<-/o/-<-+
你不需要復位狀態，而是一個包羅萬象的反思你的起始狀態標記[^g]過渡。嚴格遵循dfa定義，您需要使用|Σ|-1轉換，每個標記都使用除g以外的一個字母字符。類似地從S1到start轉變爲標記爲[^g]和從S1自身標記爲g保證在遇到模式的可能實例的前綴之後進行適當的「重置」。你可以捕捉到所有非重疊的模式實例（它們都是這個特定模式的實例）
當然這很快會變得比這個玩具例子複雜得多，這就是爲什麼標準正則表達式 - nfa-> dfa的結構通常被採用
另一種策略是在沒有增強的情況下采用原始的dfa，並且每次離開start時產生一個子進程，子進程應用與父進程相同的dfa，句子以轉換離開開始狀態的字符開始。
This sound很像你以前的問題：http://stackoverflow.com/questions/15489338/difference-between-pattern-matching-and-pattern-searching-in-terms-of-dfa-regex。 – 2013-03-19 00:42:01
@OliCharlesworth他們有關係。但是這個問題是關於給定搜索正則表達式的實現策略。前面的問題是關於搜索和匹配之間的一般差異。解決前一個可以幫助這個。 – JackWM 2013-03-19 00:55:02