正则表达式证明

Question

我能否获得关于如何证明任何正则表达式A和B的提示

A（BA）* =（AB）* A

我试图通过归纳来实现，但是在基本情况下我被卡住了，

Answer 1

它与感应效果很好。

基本情况是*为零重复：

A (BA)^0 = A = (AB)^0 A

对于一个重复，请注意，您可以将AB分解为A，然后将BA重复零次，然后将B：

A (BA)^1 = A B (AB)^0 A = ABA = AB A = (AB)^1 A

这可以一概而论：您始终可以从任何A中剥离第一个B和最后一个(AB)^n并在其中找到(BA)^(n-1)：AB AB AB与A BA BA B相同。

A (BA)^n = A B (AB)^(n-1) A = (AB)^1 (AB)^(n-1) A = (AB)^n A