regex - 试图找到一种算法，它需要两个正则表达式并判断它们是否等价

Question

我试图通过给定两种语言 L1 和 L2 来确定它们是否等效 (L1 = L2)，从而找出算法是什么。

正如我所发现的，想出一个非常困难，尽管我很确定它需要首先转换为 DFA，然后将它们每个都减少到最小的 DFA。

此外，我知道如果 L1 - L2 和 L2 - L1 为空，则 L1 = L2。

这里有人擅长理论吗？

Answer 1

您可以找到用于测试 r.e. 的相当有效的算法的描述。这里的平等:

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

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