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

您可以找到用于测试r.e.的合理有效算法的描述。平等在这里： http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.5058v1.pdf 挖掘文章的参考资料，找出效率较低但更容易实施的其他解决方案。     

这是一个概念上简单的答案（假设L1和L2是常规的）。 1）分别找到L1和L2的DFA D1和D2。 2）通过交换接受/不接受状态从D1和D2构造D'1和D'2（注意D'1完全接受~L1和D'2接受~L2，其中〜表示“补充”） 3）使用标准产品结构三次产生一个完全接受（L1交叉~L2）联合的DFA（L2交叉~L1） 4）检查第3部分中的DFA是否接受任何字符串，方法是从开始状态检查每个接受状态是否可达。 5）如果第3部分的DFA接受任何字符串，则L1＆lt;> L2。否则，L1 = L2 您可以使用大量的启发式方法来加快速度，但从概念上讲，这可能是最简单的算法。第3部分中产品构造的一个很好的参考是Dexter Kozen的“Automata and Computability”。