# How to prove an identity of regular expressions

I am in trouble how to prove that these two regular expressions are equivalent. I know what are closures and all the basics of automata. But the problem is I don't know the method or way of solving this kind of problem.

Question:

Prove that R.H.S regular expression is same as L.H.S

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

• You have certainly be taught that a) every regular expression can be converted into an NFA and b) every regular language has a unique minimal DFA. Use these facts! – Raphael Oct 20 '16 at 17:15

As an example, let us prove the identity $$a(ba)^*b = ab(ab)^*.$$ Denote the language of a regular expression $r$ by $L[r]$. A word $w$ belongs to $L[a(ba)^*b]$ if there exists $n \geq 0$ such that $w = a(ba)^nb$. Now $w = a(ba)^nb = (ab)^{n+1} = ab(ab)^n \in L[ab(ab)^*]$. Similarly, a word $w$ belongs to $L[ab(ab)^*]$ if there exists $n \geq 0$ such that $w = ab(ab)^n$. Now $w = ab(ab)^n = (ab)^{n+1} = a(ba)^nb \in L[a(ba)^*b]$.
(You can prove the various identities I used, such as $(ab)^{n+1} = a(ba)^nb$, by induction on $n$.)
Your particular identity states that if a word over $\{a,b\}$ contains an $a$ followed by $b$ (with possibly letters separating them) then it contains the substring $ab$, and vice versa. You should start by understanding why this holds.
• My examples contain no intersections. I encourage you to obtain a firm understanding of regular expressions. Before being able to solve the exercise you should understand what a regular expression like $(a+b)^*ab(a+b)^*$ stands for. – Yuval Filmus Oct 20 '16 at 16:31