0

例如，正则表达式go*d是一个模式将匹配字符串，如gd, god, good...

你可以想象它的 DFA 就像一个三态机。

当它用于模式搜索时，例如给定句子xxxxgodxxxxgoodxxx，DFAgo*d似乎不起作用。x在这个三态 DFA 中，偶数字符是未定义的。

我们可以想象一个带有额外“重置”状态的 4 状态 DFA 可以在这里工作。也就是说，当遇到未定义的字符时，进入这个“重置”状态。

问题是模式搜索工具如何使用正则表达式实现搜索目的go*d？

4

1 回答 1

0

给定简单的三态匹配器

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

您不需要重置状态，而是需要在开始状态上标记为[^g]. 严格遵循 dfa 定义，您需要|Σ|-1每个转换都标有一个字母字符，而不是g. 同样，从标记S1到start标记[^g]以及从标记S1到自身的转换g保证在遇到模式可能实例化的前缀后正确“重置”。类似地增强accept状态，您将捕获所有非重叠模式实例化（它们都是此特定模式的所有实例化。

当然，这很快变得比这个玩具示例复杂得多，这就是为什么通常使用标准的 regex->nfa->dfa 构造。

另一种策略是在没有增强的情况下使用您的原始 dfa，并在您每次离开该start州时生成一个子进程。子进程应用与其父进程相同的 dfa，将其应用于以使转换离开起始状态的字符开头的给定句子。

于 2013-03-27T19:12:43.460 回答