HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to prove an identity of regular expressions

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
identityregularexpressionsprovehow

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#64886, answer score: 2

Revisions (0)

No revisions yet.