regex - 所有正则表达式都会停止吗？

Question

对于某些输入字符串，是否有任何正则表达式可以永远搜索匹配项？

Answer 1

对于有限输入，没有不会停止的正式正则表达式。

任何正式的正则表达式都可以转换为确定性有限自动机。 DFA 一次读取一个字符，在输入结束时，您要么处于接受状态，要么处于非接受状态。如果状态正在接受，则输入与正则表达式匹配。否则，它不会。

现在，大多数“正则表达式”库都支持非正则表达式的内容，例如反向引用。只要您远离这些功能，并且输入有限，就可以保证停止。如果你不......取决于你正在使用什么，你很可能无法保证停止。例如，Perl 允许插入任意代码，并且不能保证任意的图灵机等效代码会停止。

现在，如果输入是无限的，那么可以找到永远不会停止的平凡正则表达式。例如，“.*”。