0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you need anything clarified? $\endgroup$ – mdenton8 Nov 30 '14 at 18:42
  • $\begingroup$ Using automata: build minimal DFAs for both languages, show they are isomorphic. $\endgroup$ – G. Bach Sep 16 '15 at 8:43
3
$\begingroup$

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.

$\endgroup$

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.