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

Question

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

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

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

有理论的人在这里好吗？

Answer 1

您可以在此处找到用于测试 re 相等性的相当有效的算法的描述：

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

深入研究文章的参考文献，找到其他可能效率较低但更容易实施的解决方案。