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.


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)^* $$

  • 2
    $\begingroup$ 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! $\endgroup$
    – Raphael
    Oct 20, 2016 at 17:15

1 Answer 1


Regular expressions stand for languages. To show that two languages are equal, we show that every string in the first also belongs to the second, and vice versa.

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.

  • $\begingroup$ Can you elaborate any identity with Union like (a+b)* = some other identity . I understand above example $\endgroup$ Oct 20, 2016 at 16:29
  • $\begingroup$ 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. $\endgroup$ Oct 20, 2016 at 16:31
  • $\begingroup$ Sorry i mean you give example of ab So I need some help about (a+b)* = (a+b)* + a* $\endgroup$ Oct 20, 2016 at 16:34
  • $\begingroup$ Unfortunately I can't act as your tutor. I suggest looking up one in your place of study. $\endgroup$ Oct 20, 2016 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.