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

Question

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

我怀疑既然存在这种情况，我的问题将减少为停止问题，但我真的很想错了。

Answer 1

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

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

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