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

Question

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

Answer 1

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

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

现在，大多数“正则表达式”库支持不是正则表达式的东西，如反向引用。只要你远离这些功能，并有一个有限的输入，你肯定会停下来。如果你不......取决于你正在使用的是什么，你可能不能保证停下来。 Perl允许插入任意代码，例如，任意的图灵机等价代码不保证停止。

现在，如果输入是无限的，那么可以发现不会停止的微不足道的正则表达式。例如，“.*”。

Answer 2

不要在你所描述的感觉，你可以有占用资源的负荷，并最终杀死正则表达式引擎的一些非常低效的正则表达式，这是不一样的停止。

我不认为停止在这里真的适用，因为这篇文章的其他评论者如此敏锐地指出。 http://en.wikipedia.org/wiki/Halting_problem

Answer 3

根据this question，每个正则表达式停止。

Answer 4

我想，这是不可能找到一个不停止的正则表达式。

输入的大小是有限的。正则表达式的任何匹配子组的最大大小在最大值时是您输入的大小。

除非所使用的算法是非常愚蠢的（去在案件多次），匹配子组的数量，将太，是有限的。

所以，它会停下来。

Answer 5

我无法想象，将永远解析，虽然无限长的字符串将永远被解析的输入字符串。鉴于正则表达式可以描述规则语言，这可能是一组无限的单词，那么正则表达式可以描述无限单词的语言，包括无限长的单词。但是，没有输入字符串可以无限长，所以在某些时候它不得不停止。

例如，如果A * B在语言接受，你有一个无限长的“一个的字符串，那么是的，正则表达式将永远不会停止。但实际上，这是不可能的。

Answer 6

形式正则表达式实际上是一种描述用于解析字符串的确定性有限自动机的方法。如果DFA在输入结束时处于接受状态，则正则表达式“匹配”。由于DFA按顺序读取输入，因此在达到输入末尾时会始终停止，并且是否存在匹配仅仅是检查停止在哪个DFA状态的问题。

子字符串匹配实际上是相同的，除了不是被迫在字符串的一次读取结束时被暂停，而是在读取每个可能的子字符串一次后强制停止 - 仍然是有限的情况。 （是的，大多数正则表达式引擎都是以一种更优化的方式实现这一点，而不仅仅是将每个可能的子字符串都放在DFA中 - 但在概念上它的限制仍然存在）。

因此在其中DFA不会终止唯一可能的情况是，如果输入为无限大，这通常被认为是超出了停机问题的范围。

Answer 7

是的。

正则表达式可以用有限状态机表示。每次接收到原子输入时，都会导致任何定义良好的FSM转换到已知状态。

例外情况是当您有无限输入时，但这不适用于暂停问题，因为它处理有限的输入。当你有一个有限的状态机和有限的输入时，总是可以确定你的机器是否会停下来。

http://en.wikipedia.org/wiki/Finite_state_machine

Answer 8

1丹尼尔的回答是：所有的有限输入导致真正的正则表达式的（即，没有反向引用或其他非正则表达式特性）暂停，和正则表达式的等效于的DFA。

奖励：正则表达式匹配可以是简单和快速 （但是慢用Java，Perl和PHP，Python和Ruby，...）

http://swtch.com/~rsc/regexp/regexp1.html

注意，两个图在文章的顶部在y轴上有不同的比例尺：一个是秒，另一个是微秒！