Simplification of REGEX expression

Question

I need to prove or disprove the below REGEX

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

I have a strong gut feel that they are equivalent, but how do i give a step by step proof using the laws of REGEX.

Answer 1

First understand what this formal languages mean:

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

From LHS, (RS + R)* uses to generate any combinations of RS and R including ^ epsilon. Some example strings are {^, RS, RSRS, RRRS, RSR,...}: strings always starts from R but can end with either S or R - we can describe in English: R can appear in any combination where S is always followed by one R (two consecutive S are not possible).

And, complete LHS's re (RS + R)*R means string always terminates with R.

Now, consider following examples:

1. R + S is same as S + R, it is basically union
2. But RS can't be written as SR, order is important in concatenation
3. (RS)R can be written as R(SR)
4. (RS)*R can be written as R(SR)*, both are same that is RSRSRS...SR
5. (AB + AC) can be written as A(B + C)
6. (AB + A) can be written as A(B + ^), this is because A = ^A = A^
7. (BA + A) can be written as (B + ^)A.

Formal Proof:

   (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 

Same steps are correct for regex.

Answer 2

Yes, the first regex is equal to the second.

I cannot give you the formal proof because I am not that well versed in proving, but I can give you a hint that those expressions are equal.

You can enumerate examples manually, like so:

1.) Can I produce e(epsilon)?

• (RS + R)* can be epsilon

• R cannot be epsilon

• concatenate the 2 = (epsilon)R or simply = R

So the most basic string you can form is 'R'. Now continue the process of deriving strings and you'll come up with the conclusion that the 2 regex are equal.