[Solved]: Proof of equivalence of regular expressions (0 + 1)(0 + 1)* and (0 + 1)*(0 + 1)

Problem Detail: 

How would I prove that the regular expressions RS and SR where R = (0 + 1) and S = (0 + 1)* are equivalent? The '+' sign represents union of two regular expressions and two expressions RS are concatenated.

From what I know, either you must prove using existing rules about equivalence of regular expressions (example: commutativity or associativity of union) or you must prove that L(RS) is a subset of L(SR) AND L(SR) is a subset of L(RS) where L is the language denoted by the regular expression in the parentheses.

However, I am struggling to come up with a proof. Could someone give me a hint?

Asked By : Teresa

Answered By : mdenton8

Let's go with your second approach.

First note that $R^n$, for any nonnegative integer $n$, is in $L(S)$.

If the string $w$ is in the first language, $L(RS)$, then we know that $w$ can be written as the concatenation of some string in $R$ and some string in $S$. This concatenation is denoted $(0 + 1)(0 + 1)^n$ (for some nonnegative integer $n$), which equals $RR^n$ which equals $R^{n+1}$, which equals $R^nR$, which we know is in the language $L(SR)$ (since $S=R^*$).

The reverse direction is more or less the same thing.

---

Edit: Another interesting way of proving this is to prove $L(RS) = L(S)$ and $L(SR) = L(S)$.

To prove $L(RS) = L(S)$, take any string in $L(RS)$. It can be written as $RR^n$ for some nonnegative integer $n$. Now this equals $R^{n+1}$, which is of course in $L(S)$. So we have that $L(RS)\subseteq L(S)$.

Now take any string in $L(S)$. It can be written as $R^m$ for some nonnegative integer $m$. This is equivalent to $RR^{m-1}$, which is in $L(RS)$, so we know that $L(S)\subseteq L(RS)$.

Therefore we have $L(S)=L(RS)$.

We can prove $L(S)=L(SR)$ in a very similar way. Therefore $L(RS)=L(SR)$.

---

The actual difficulty and intuition behind the proof is fairly trivial, but putting the proof into words is harder. The proof amounts to proving some kind of exponent law for the Kleene star. We don't have an actual exponent law for the Kleene star, so the key part of the proof is simply isolating a single arbitrary string in the language, and then we have the finite integer exponents and we can just use the normal exponent laws.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33633

3.2K people like this

 Download Related Notes/Documents