正则表达式 – 试图找到一个算法,它采用2个正则表达式并告诉它们

发布时间：2020-12-13 21:53:39 所属栏目：百科来源：网络整理

导读：我试图通过给出两种语言L1和L2来确定算法是什么,以确定它们是否相等(L1 = L2). 我发现它很难想出一个,虽然我很确定它需要首先转换为DFA,然后将它们减少到最小的DFA. 另外,我知道如果L1-L2和L2-L1为空,则L1 = L2. 有理论的人在这里好吗？您可以找到用于测试r

我试图通过给出两种语言L1和L2来确定算法是什么,以确定它们是否相等(L1 = L2).

我发现它很难想出一个,虽然我很确定它需要首先转换为DFA,然后将它们减少到最小的DFA.

另外,我知道如果L1-L2和L2-L1为空,则L1 = L2.

有理论的人在这里好吗？

您可以找到用于测试r.e.的合理有效算法的描述.平等在这里：

http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.5058v1.pdf

挖掘文章的参考资料,找出效率较低但更容易实施的其他解决方案.

（编辑：李大同）

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