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)* 用于生成epsilon （包括RSepsilon ）的任意组合。一些示例字符串是：字符串总是从 开始，但可以以or结尾- 我们可以用英语描述：可以出现在任何组合中，其中总是后跟一个（不可能连续两个）。R^{^, RS, RSRS, RRRS, RSR,...}RSRRSRS

并且，完整的 LHS 的 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 = R(SR + R)*

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