所有正则表达式都停止吗? [英] Do all regular expressions halt?

问题描述

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

Is there any regular expression that will, for some input string, search for a match forever?

推荐答案

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

For a finite input, there is no formal regular expression that will not halt.

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

Any formal regular expression can be translated into a Deterministic Finite Automata. A DFA reads the input one character at a time, and, at the end of the input, you are either in an accepting state or in a non-accepting state. If the state is accepting, then the input matches the regular expression. Otherwise, it doesn't.

现在，大多数正则表达式"库支持的东西不是正则表达式，例如反向引用.只要您远离这些功能并输入有限的内容，就可以保证您停止运行.如果您不...根据所使用的内容而定，则很可能无法保证暂停.例如，Perl允许插入任意代码，并且不能保证任意的图灵机等效代码都不会停止.

Now, most "regular expression" libraries support things which are not regular expressions, such as back references. As long as you keep away from those features, and have a finite input, you are guaranteed a halt. If you don't... depending on exactly what you are using, you might well not be guaranteed a halt. Perl allows arbitrary code to be inserted, for instance, and arbitrary, turing-machine equivalent code is not guaranteed to halt.

现在，如果输入是无限的，则可以找到永远不会停止的琐碎的正则表达式.例如，".*".

Now, if the input is infinite, then trivial regular expressions can be found which will never halt. For example, ".*".

这篇关于所有正则表达式都停止吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！