regular expression algebra

Question

prove the identity:     (a*ab + ba)* a* = (a + ab + ba)*

Answer 1

Proving the identities of Regular expression is a very difficult task. Its belong to the PSPACE complexity. Here is the reference. Link1 and Link2. 

There is an algorithm to determine whether they are equal:

1. Construct NFA-lambdas corresponding to each RE using Kleene's theorem.
2. Construct DFAs for each using the subset/powerset construction
3. (optional) Minimize the DFAs using a standard DFA minimization algorithm. 
4. Construct DFAs for L(M1) \ L(M2) and L(M2) \ L(M1) using the Cartesian Product Machine construction
5. (Optional) Minimize these CPMs.
6. Determine whether each one accepts any strings by testing all strings over alphabet E of size no greater than |Q| (works due to the pumping lemma for regular languages)

For the Gate Points of View, if you want to prove that two regular expression same or not then prove it by contradiction. It means that generate a string from one of the grammar which can not be generated by the other grammar. A general advice is that you should always start from the most basic string.

This about the given regular expression. The most basic string which can be generated by the RHS regular expression is $\{ \epsilon, a, ab, ba \} $ 

Now check if this string can be generated from LHS regular expression or not? Yes they all can be generated. 

You can think like this. Now think some string which can be generated by the LHS regular expression and see that can be generated by RHS regular expression or not. That's it. 

Comments

string, say (a^2)b is generated by LHS but not by RHS. Is it so?

---

No dude, RHS can also generate the aab.