正则表达式 – 是否存在可以确定一种常规语言是否匹配任何其他常

发布时间：2020-12-14 06:33:39 所属栏目：百科来源：网络整理

导读：假设我们有正则表达式：你好W. * rld 你好世界。*世界。* W. * 我想最小化匹配任意输入所需的正则表达式数量。要做到这一点，我需要找到一个正则表达式是否匹配任何与另一个表达式匹配的输入。那可能吗？ Billy3 任何正则表达式都可以链接到DFA – 您可

假设我们有正则表达式：

>你好W. * rld
>你好世界
>。*世界
>。* W. *

我想最小化匹配任意输入所需的正则表达式数量。

要做到这一点，我需要找到一个正则表达式是否匹配任何与另一个表达式匹配的输入。那可能吗？

Billy3

任何正则表达式都可以链接到DFA – 您可以最小化DFA，并且由于最小表单是唯一的，因此您可以决定两个表达式是否相等。 Dani Cricco指出了Hopcroft O(n log n)算法。还有另一个改进的算法，由Hopcroft和Craft来测试O(n)中两个DFA的等价性。

对于这个问题的一个很好的调查和一个有趣的方法，我推荐了来自arXiv的文章Testing the Equivalence of Regular Languages。

稍后编辑：如果你对正则表达式有兴趣包含而不是等价性，我遇到了一篇可能感兴趣的论文：Inclusion Problem for Regular Expressions – 我只是撇开它，但它似乎包含一个多项式时间算法的问题。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!