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

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

现在,如果输入是无限的,那么可以找到不会停止的简单的正则表达式.例如,”.*”.