3

实现正则表达式匹配有三种不同的解决方案：DFA、NFA 和 Backtracking。我正在寻找示例：

  • 一个正则表达式，可以用 DFA 解决，以及为什么 DFA 就足够了。
  • 一个正则表达式，它需要 NFA 以及需要 NFA 的原因。
  • 一个正则表达式，它需要回溯以及需要回溯的原因。

推荐一些关于这个主题的优秀文献也很好。

4

2 回答 2

4

我想回溯这个词有不止1个含义-甚至'.*a'必须回溯以匹配字符串"lalaiiiiiii" （因为 .* 将首先匹配整个字符串-因此 a 不会匹配任何内容-只有这样它才会一次放弃一个字符，所以最后一场比赛是 "lala"）

我强烈推荐http://www.regular-expressions.info/

于 2012-02-16T00:44:26.020 回答
-3

到目前为止我发现的是：

  • 每个可以用 NFA 实现的正则表达式也可以用 DFA 实现。每个 NFA 都可以转换为 DFA。

  • 需要回溯的正则表达式是正则表达式，其中包含反向引用，例如/(a)\1/.

于 2011-12-13T16:31:32.640 回答