我需要证明或反驳下面的正则表达式
(RS + R )* R = R (SR + R)*
// or, for programmers:
/(RS|R)*R/ == /R(SR|R)*/
我有一种强烈的直觉,认为它们是等价的,但我如何使用 REGEX 定律逐步证明。
最佳答案
首先理解这个形式语言是什么意思:
(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
结尾.
现在,考虑以下示例:
-
R + S
与S + R
相同, 它基本上是联盟 - 但是
RS
不能写成SR
, 顺序在连接中很重要 -
(RS)R
可以写成R(SR)
-
(RS)*R
可以写成R(SR)*
, 两者相同即RSRSRS...SR
-
(AB + AC)
可以写成A(B + C)
-
(AB + A)
可以写成A(B + ^)
, 这是因为A = ^A = A^
-
(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
相同的步骤对于正则表达式也是正确的。
关于regex - REGEX 表达式的简化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21717298/