snippetMinor
How to prove an identity of regular expressions
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)^* $$
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.
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.