Dan*_*ral 31
对于有限输入,没有正式的正则表达式不会停止.
任何正式的正则表达式都可以转化为确定性有限自动机.DFA一次读取输入的一个字符,并且在输入结束时,您处于接受状态或处于非接受状态.如果状态正在接受,则输入与正则表达式匹配.否则,它没有.
现在,大多数"正则表达式"库都支持非正则表达式的东西,例如反向引用.只要您远离这些功能并且输入有限,就可以保证停止.如果你不......根据你使用的具体内容,你可能无法保证停止.例如,Perl允许插入任意代码,并且不保证任意的图灵机等效代码可以停止.
现在,如果输入是无限的,那么可以找到永远不会停止的普通正则表达式.例如," .*".
正式正则表达式实际上是一种描述用于解析字符串的确定性有限自动机的方法.如果DFA在输入结束时处于接受状态,则正则表达式"匹配".由于DFA按顺序读取其输入,因此当它到达输入的末尾时它将始终停止,并且是否存在匹配仅仅是检查它停止的DFA的状态.
子串匹配实际上是相同的,除了不是在字符串的一个通读结束时被强制停止,而是在读取每个可能的子字符串之后强制停止DFA - 仍然是有限的情况.(是的,大多数正则表达式引擎以更优化的方式实现这一点,而不仅仅是在DFA中抛出每个可能的子字符串 - 但从概念上讲,它仍然存在极限).
因此,DFA不会停止的唯一可能情况是输入是无限的,这通常被认为超出了停止问题的范围.