试图找到一种算法，它接受 2 个正则表达式并判断它们是否等价
我试图通过给定两种语言 L1 和 L2 来确定它们是否等效（L1 = L2）来找出算法是什么。
正如我发现的那样，想出一个是非常困难的，尽管我很确定它需要首先转换为 DFA，然后将它们每个都减少到最小的 DFA。
另外，我知道如果 L1 - L2 和L2 - L1 为空，则 L1 = L2。
这里有人擅长理论吗？
I'm trying to find out what the algorithm would be by being given two languages L1 and L2 to determine if they are equivalent (L1 = L2).
It's surprisingly difficult to come up with one as I've found, although I am pretty sure it needs to be converted to a DFA first and then reduce each of them to a minimal DFA..
Also, I know that if L1 - L2 and L2 - L1 are empty, then L1 = L2.
Anyone good with theory here?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是一个概念上简单的答案（假设 L1 和 L2 是常规的）。
1) 分别为L1和L2找到DFA D1和D2。
2) 通过交换接受/不接受状态，从 D1 和 D2 构造 D'1 和 D'2（注意 D'1 完全接受 ~L1，D'2 接受 ~L2，其中 ~ 表示“补集”）
3) 使用标准产品构造三次，以生成完全接受 (L1 相交 ~L2) 并集 (L2 相交 ~L1) 的 DFA
4) 通过从一开始就检查每个接受状态的可达性，检查第 3 部分中的 DFA 是否接受任何字符串状态。
5)如果第3部分中的DFA接受任何字符串，则L1<> L2。否则，L1=L2
您可以使用大量启发式方法来加快速度，但从概念上讲，这可能是最简单的算法。第 3 部分中的产品构建的一个很好的参考是 Dexter Kozen 的“Automata and Computability”。
Here's a conceptually simple answer (assuming L1 and L2 are regular).
1) Find DFAs D1 and D2 for L1 and L2 respectively.
2) Construct D'1 and D'2 from D1 and D2 by swapping accepting/non-accepting states (note that D'1 accepts exactly ~L1 and D'2 accepts ~L2 where ~ means "complement of")
3) Use the standard product construction three times to produce a DFA that accepts exactly (L1 intersect ~L2) union (L2 intersect ~L1)
4) Check to see if the DFA from part 3 accepts any strings by checking each accepting state for reachability from the start state.
5) If the DFA from part 3 accepts any strings, then L1 <> L2. Otherwise, L1=L2
There are a huge number of heuristics you could use to speed this up, but conceptually, this is probably the simplest algorithm. A good reference for the product construction in part 3 is "Automata and Computability" by Dexter Kozen.
您可以在这里找到用于测试相等性的相当有效的算法的描述：
http: //arxiv.org/PS_cache/arxiv/pdf/0907/0907.5058v1.pdf
深入研究文章的参考文献，找到其他可能效率较低但更容易实现的解决方案。
You can find a description of a reasonably efficient algorithm for testing r.e. equality here:
http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.5058v1.pdf
Dig through references of the article to find other solutions that may be less efficient, but easier to implement.