如何证明(或找到)两个正则表达式是相同还是等同？

Question

例如,在给我的作业中,我们被要求查明两个正则表达式是否相等.

(a+b+c)*  and ((ab)**c*)*

我的问题是如何做到这一点？如果我绘制两者的转换图,然后通过它运行几个字符串并显示两个TG都能够接受它,这是否足以证明？如果没有,我该怎么办？对此有一种数学/公理方法吗？

提前致谢.

编辑:还有一件事我想清楚哪一点与这个问题有关.下面照片中描绘的两个FA是否相同？

即上图中的(1)和(2)是否相同？

Answer 1

有一个算法来确定它们是否相等：

1. 使用 Kleene 定理构建对应于每个 RE 的 NFA-lambda
2. 使用子集/幂集构造为每个构造 DFA
3. （可选）使用标准 DFA 最小化算法最小化 DFA。
4. 使用笛卡尔积机器构造为 L(M1) \ L(M2) 和 L(M2) \ L(M1) 构造 DFA
5. （可选）最小化这些每千次展示费用。
6. 通过测试大小不大于 |Q| 的字母 E 上的所有字符串来确定每个字符串是否接受任何字符串。（由于常规语言的抽水引理而起作用）

不需要新奇或天才；您可以编写一个程序来执行此操作（尽管在实践中，使用 powerset 构造可能很笨拙，并且未能在两个步骤中都最小化可能代价高昂）。

编辑：是的，这些 DFA 是相同的。第一个只是第二个的速记符号。