Show that two regular expressions are equivalent in Automata Theory without using DFAs

Question

I have been trying to prove that two regex are equivalent. I know that two regex are equivalent if they define the same language. But i am not getting my hands of way to prove it without using DFAs.

For example, i have the problem to prove that the following are equivalent.

(a + b)*a(a + b)*b(a + b)* = (a + b)*ab(a + b)*

I know both of these define the language having atleast one 'a' and one 'b'.

The same is the case with the following.

(a + b)*ab(a +b)* + b*a* = (a + b)*

Any help will be appreciated.

Thanks

Answer 1

You should be able to prove them using the identities on slide 16 of this regex lecture. In particular, I'd recommend clever use of the last equality of the 9th identity there, R* = RR*+e.

By the way, the first language is not precisely "at least one 'a' and one 'b'". For example, 'ba' is not in the language, but has at least one 'a' and one 'b'.

Answer 2

I think in first language there is (a+b)* in the middle which mean that this is arbitrary so we can ignored the arbitrary (a+b)* so it will become equivalent