我一直试图证明两个正则表达式是等价的。我知道如果两个正则表达式定义相同的语言，它们是等价的。但是如果不使用 DFA，我就无法证明这一点。
例如，我有问题要证明以下是等价的。
(a + b)*a(a + b)*b(a + b)* = (a + b)*ab(a + b)*
我知道这两种语言都定义了至少有一个“a”和一个“b”的语言。
下面的情况也是如此。
(a + b)*ab(a +b)* + b*a* = (a + b)*
任何帮助将不胜感激。
谢谢
问问题
2078 次
2 回答
0
您应该能够使用 此正则表达式讲座幻灯片 16 上的身份证明它们。特别是，我建议巧妙地使用第 9 个恒等式的最后一个等式，R* = RR*+e。
顺便说一句，第一语言并不完全是“至少一个'a'和一个'b'”。例如，“ba”不在语言中，但至少有一个“a”和一个“b”。
于 2015-09-03T03:33:32.083 回答
0
我认为在第一语言中，中间有 (a+b)* 这意味着这是任意的，所以我们可以忽略任意的 (a+b)* 所以它会变得等价
于 2020-12-20T11:44:33.747 回答