我正在研究一些正则表达式的问题，当对某个输入进行匹配时，它们可能会以指数级的时间运行。例如，
我的问题是，为什么
"aaaa"匹配，但不能匹配'b'，失败（回溯）
"aaaa@"匹配，'b'失败（回溯）
"aaa@a"匹配，'b'失败（回溯）
"aaa@a@"匹配，'b'失败（回溯）
...
"@a@a@a@a@"匹配，'b'失败（回溯）
尝试所有可能的ε和a的组合，导致路线指数级扩大。
从NFA中删除ε转换似乎是有道理的，但我认为这会使
非常感谢您提前的帮助！
(a*)*和(a|a)*在与字符串aaaaab匹配时可能会出现'灾难性回溯'的情况——对于匹配字符串中每一个额外的'a'，尝试匹配该字符串所需的时间就加倍。只有引擎使用回溯/NFA方法在失败之前尝试树中所有可能的分支，例如PCRE所使用的方法，才会出现这种情况。我的问题是，为什么
(a?)*不会出现这种漏洞？根据我对回溯的理解，在字符串"aaaab"中应该发生的基本上就是(a|a)*中发生的情况。如果我们使用标准的Thomspson NFA构造来构建NFA，则对于每个ε转换，引擎都必须继续采取它们并以与两个a的情况相同的方式进行回溯吗？例如（省略了一些步骤，其中@替换ε）："aaaa"匹配，但不能匹配'b'，失败（回溯）
"aaaa@"匹配，'b'失败（回溯）
"aaa@a"匹配，'b'失败（回溯）
"aaa@a@"匹配，'b'失败（回溯）
...
"@a@a@a@a@"匹配，'b'失败（回溯）
尝试所有可能的ε和a的组合，导致路线指数级扩大。
从NFA中删除ε转换似乎是有道理的，但我认为这会使
(a*)*模式中所有的非确定性都消失。然而，这种模式肯定是脆弱的，所以我不太确定发生了什么！非常感谢您提前的帮助！
编辑：Qtax 指出，在使用传统回溯时，NFA 遍历时仍然不能出现 epsilon，否则 (@)* 将会一直尝试匹配。那么，有哪种 NFA 实现可能导致 (a*)* 和 (a|a)* 呈指数增长，而 (a?)* 则不是呢？这才是问题的核心。
(a*)*（即未经优化的引擎）等模式影响的引擎上，(a?)*似乎没问题 - 为什么？！ - Jarmexa然后对每个重复匹配空字符串），那么正则表达式永远不会失败，因为您可以无限地重复()*。 - Qtax()*的一个好处是，我发现很难理解现有实现如何进行优化以防止这种情况发生。通过Thompson构造（包括e-moves）简单地构建NFA，然后尝试通过它进行回溯的非常天真的实现，永远不会因你提到的()*原因而终止，那么他们做了什么导致(a?)*成功，但(a*)*失败？它不能简单地删除所有e-moves，因为我认为这会导致(a*)*变得确定。 - Jarmex^(a*)*$和^(a?)*$。例如命令（win）：perl -Mre=debug -e "'aaab' =~ /^(a?)*$/"。 - Qtax