正则表达式 – 是否可以可靠地确定给定的正则表达式是否匹配任何
发布时间：2020-12-14 06:22:58 所属栏目：百科 来源：网络整理
导读：参见英文答案 Does an algorithm exist which can determine whether one regular language matches any input another regular language matches?4个 我想采用用户输入正则表达式并确定它是否匹配任何字符串,即它是否“缩减”为.要么 .*？ 我怀疑自从this e
|
参见英文答案 >
Does an algorithm exist which can determine whether one regular language matches any input another regular language matches?4个
我想采用用户输入正则表达式并确定它是否匹配任何字符串,即它是否“缩减”为.要么 .*？ 我怀疑自从this exists以来,我的问题将减少到停止问题,但我真的想错了.
我认为你想要的东西与正则表达式的语法以来的Halting问题类似.考虑到自动机识别的字母和语言是有限的,您仍然可以使用虚拟算法来尝试您的语言的每个世界,并测试正则表达式是否能够识别它.
实际上,这种方法的复杂性非常糟糕,但是由于输入的数量是可枚举的,因此您在Halting问题中没有任何“未定义”状态. 我实际上不知道这个虚拟算法的更好版本是否存在,但我希望我回答你关于与Halting问题相似的问题. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |