正则表达式证明

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

这可以概括：您始终可以从任何(AB)^n中剥离第一个A和最后一个B，并在里面找到(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