regex - REGEX 表达式的简化

Question

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

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

我有一种强烈的直觉，认为它们是等价的，但我如何使用 REGEX 定律逐步证明。

Answer 1

首先理解这个形式语言是什么意思:

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

来自 LHS，(RS + R)*用于生成 RS 的任意组合和 R包括 ^ epsilon。一些示例字符串是 {^, RS, RSRS, RRRS, RSR,...} : 字符串总是从 R 开始但可以以 S 结尾或 R - 我们可以用英文描述:R可以出现在 S 的任何组合中后面总是跟一个 R (两个连续的 S 是不可能的)。

然后，完成 LHS 的回复 (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 

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