我想采用用户输入正则表达式并确定它是否匹配任何字符串,即它会"减少"到.+或.*？
我怀疑,既然存在,我的问题将减少到停止问题,但我真的想错了.
我不认为你想要的与正则表达式语法以来的停止问题类似。考虑到您的自动机识别的字母表和语言是有限的，您仍然可以使用虚拟算法来尝试您的语言的每个世界并测试正则表达式是否能够识别它。
实际上，这种方法非常复杂，但由于输入的数量是可枚举的，因此在停止问题中不会出现任何“未定义”状态。
我实际上不知道这个虚拟算法是否存在更好的版本，但我希望我回答了您关于与停止问题相似的问题。