3
$\begingroup$

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

$\endgroup$
  • 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 '16 at 17:15
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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