正则表达式A(B + C*)== AB + A(C*)

Question

我知道左边的分配规则这个正则表达式:A(B + C)

可以这样写:AB + AC

我的问题是下一个.在这个例子中可以使用左分布的规则:A(B + C*)

这样我就可以得到:AB + A(C*)

或者我得到这样的东西:AB + AC*

谢谢

Answer 1

AB + A(C*)绝对正确(并且AB + AC*几乎肯定也是正确的,取决于优先级*).

有问题的正则表达式是A ( B + C* )⇔ A ( B + (C*) ).如果我们使用c= C*作为替换,我们可以将原始正则表达式编写为A ( B + c ),现在很明显我们可以使用左分布规则.一气呵成地完成所有步骤:

A ( B + C* ) <=> A ( B + (C*) ) <=> AB + A(C*) <=> AB + AC*

(为了说明目的,这里有更多的工作而不是必要的工作,我用<=>的意思是"相当于".)

我们还可以看看有问题的正则表达式匹配(它不是证明,但它是一个很好的证明它们是等价的):

• A(B + C*)比赛A随后由单个B或任意数量的C赛格AB,A,AC,ACC,ACCC...
• AB + A(C*)无论是匹配AB或A后跟任意数量的C赛格AB,A,AC,ACC,ACCC...

那些是完全相同的东西.