时间戳

首页 > 解决方案 > 正则表达式证明

regex - 正则表达式证明

问题描述

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

A(BA)* = (AB)*A

我试图用归纳法来做，但在基本情况之后我被卡住了，

标签： regexregular-languageproof

解决方案

它适用于感应。

基本情况是*零重复：

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和最后一个并找到inside:与.B(AB)^n(BA)^(n-1)AB AB ABA BA BA B

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

推荐阅读