簡化正則表達式表達

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個正則表達式是相等的結論。