World's most popular travel blog for travel bloggers.

How to prove an identity of regular expressions

, , No Comments
Problem Detail: 

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

Asked By : Syed Qasim Ahmed
Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback