简化正则表达式表达

Question

的，我需要证明或反驳以下正则表达式

(RS + R)* R = R (SR + R)* 
// or, for programmers: 
/(RS|R)*R/ == /R(SR|R)*/ 

的我有一种强烈的直觉觉得自己是等价的，但我怎么给一个循序渐进的使用正则表达式的法律一步证明。

Answer 1

先了解这个形式语言的意思：

(RS + R)*R = R(SR + R)* 

从LHS，(RS + R)*用来生成的RS和R任意组合，包括^小量。有些〔实施例字符串是{^, RS, RSRS, RRRS, RSR,...}：字符串的方式从R启动，但可以与任何S或R结束 - 我们可以用英语描述：R可以在S总是跟着一个R（连续两个S是不可能的）的任意组合冲击片雷管。

而且，完整的LSH's re (RS + R)*R表示字符串始终以R结尾。

现在，考虑下面的例子：

1. R + S是一样S + R，它基本上是工会
2. 但RS不能写成SR，为了在串联重要
3. (RS)R可写为R(SR)
4. (RS)*R可以写成R(SR)*，两者都是相同的，即RSRSRS...SR
5. (AB + AC)可以写成A(B + C)
6. (AB + A)可以写为A(B + ^)，这是因为A = ^A = A^
7. (BA + A)可以写为(B + ^)A。

正式证明：

(RS + R)*R  // LHS 
=> (R(S + ^))*R // from rule 6 
=> R((S + ^)R)* // from rule 4 
=> R(SR + R)*  // from rule 7, in revers `(B + ^)A` --> `(BA + A)` 
// RHS 

相同的步骤对正则表达式正确。

Answer 2

是的，第一个正则表达式等于第二个正则表达式。

我不能给你正式的证明，因为我不是很精通证明，但我可以给你一个暗示，那些表达式是平等的。

可以手动枚举的例子，像这样：

1）我可以产生E（小量）？

• （RS + R）*可以EPSILON

• R 1不能被EPSILON

• 串联的2 =（ε）R或简单地= R

所以你可以形成的最基本的字符串是'R'。现在继续推导字符串的过程，你会得出2个正则表达式是相等的结论。