regex - 是否可以可靠地确定给定的正则表达式是否匹配任何字符串？

Question

这个问题在这里已经有了答案:





Does an algorithm exist which can determine whether one regular language matches any input another regular language matches?

(4 个回答)


8年前关闭。




我想采用用户输入的正则表达式并确定它是否会匹配任何字符串，即它是否会“减少”为 .+或 .* ?

我怀疑是因为 this exists ，我的问题将减少到停止问题，但我真的很想错。

Answer 1

由于正则表达式的语法，我不认为您想要的类似于停机问题。考虑到字母表和自动机识别的语言是有限的，您仍然可以使用虚拟算法来尝试您语言的每个世界并测试正则表达式是否能够识别它。

在实践中，这种方法具有可怕的复杂性，但由于输入的数量是可枚举的，因此您不会在 Halting 问题中遇到任何“未定义”状态。

我实际上不知道是否存在这种虚拟算法的更好版本，但我希望我回答了您关于与停机问题的相似性的问题。