正则表达式 (a?)* 不是指数？

Question

我目前正在研究正则表达式的问题，当与某个输入匹配时，正则表达式最终会在指数时间内运行，例如 (a*)*和 (a|a)*可能会出现“catastrophic backtracking” ' 当与字符串 aaaaab 匹配时 - 对于匹配字符串中的每个额外 'a'，尝试匹配字符串所需的时间加倍。只有当引擎使用回溯/NFA 方法尝试在失败之前尝试树中所有可能的分支时才会出现这种情况，例如 PCRE 中使用的那种。

我的问题是，为什么不是 (a?)*易受伤害的？根据我对回溯的理解，字符串 "aaaab"中应该发生的事情本质上就是 (a|a)* 发生的事情。 .如果我们使用标准的 Thomspson NFA 构造来构造 NFA，那么对于发生的每个 epsilon 转换，引擎肯定必须继续采用它们并以与处理两个 a 的情况相同的方式进行回溯？例如(省略一些步骤，@ 替换 epsilon):

“aaaa”匹配，但不能匹配“b”，失败(回溯)
“aaaa@”匹配，“b”失败(回溯)
“aaa@a”匹配，“b”失败(回溯)
"aaa@a@"匹配，'b' 失败(回溯)
...
"@a@a@a@a@"匹配，'b' 失败(回溯)

尝试所有可能的 epsilon 和 a 组合，肯定会导致路由的指数爆炸？

从 NFA 中删除 epsilon 转换是有意义的，但我相信这具有从 (a*)* 中删除所有非确定性的效果。模式。但这绝对是脆弱的，所以我不完全确定发生了什么!

非常感谢您提前!

编辑: Qtax 已经指出，当使用传统回溯遍历 NFA 时，epsilons 仍然不能存在，否则 (@)*将尝试永远匹配。那么什么 NFA 实现可能会导致 (a*)*和 (a|a)*是指数的，并且 (a?)*不是这样？这真的是问题的关键。

Answer 1

好吧，经过一番侦查，我最终设法发现这归结为在 NFA 实现中使用了“障碍”。简单地说，障碍被放置在 NFA 中的战略点(例如在 NFA 构建 a* 中的“a”转换之后的节点上)。他们要求比赛从上次击中障碍的时间开始。这可以防止 NFA 陷入与无限数量的 epsilon 匹配并允许其终止的情况。

换句话说，不可能从一个障碍转到仅匹配 e-move 的同一障碍 - 如果发生这种情况，路线将被丢弃并且从前一点开始回溯。这也有副作用，即 (a?)* 不容易受到指数爆炸的影响，因为 a?第二次不能匹配空值。