# Equivalence of regular expressions

I need to prove (or disprove, but I think those are proves), that the regular expression:

r = (a+b)*b(a+b)*a(a+b)* (where + is OR and * is Kleene star)


is equivalent to those expressions:

r' = (a+b)*bb*a(a+b)*
r'' = a*b(a+b)*ab*


The prove needs to be done by two-sided containment (that is, prove that L(r) is in L(r') and vice versa). Any help would be appriciated.

-

Let $\Sigma = \{a,b \}$.

Note that $s \in L(r)$ $\iff$ $s_k \in \Sigma$ for all $k$ and there exists $i<j$ such that $s_i=b$, $s_j=a$.

A moment's reflection shows that, without loss of generality, we may assume $s_i = s_{i+1} = \cdots = s_{j-1} = b$.

If $s \in L(r') \cup L(r'')$, then it is clear that $s$ has the form $s = \omega_1 b \omega_2 a \omega_3$, where $\omega_k \in \Sigma^*$, and so $s \in L(r)$. Hence $L(r') \cup L(r'') \subset L(r)$.

Now suppose $s \in L(r)$. From the above reflection, we see that $s$ has the form $s=\omega_1b b^* a \omega_2$, with $\omega_k \in \Sigma^*$. Hence $s \in L(r')$. Now let $i$ be the first index such that $s_i = b$ and let $j$ be the last index such that $s_j = a$. (Since $s \in L(r)$ we know that such indices exist and that $i < j$.) Then $s$ has the form $a^* b \omega_1 a b^*$, with $\omega_1 \in \Sigma^*$. Hence it follows that $s \in L(r'')$.

-
what are exactly r' and rn? – DanielY Nov 22 '12 at 19:36
You defined three regular expressions in the question, $r, r', r''$. I'm not sure what you mean by 'rn'? – copper.hat Nov 22 '12 at 19:40
it's r''....and I need two seperate proves – DanielY Nov 22 '12 at 19:53
I am not sure what you want. I have shown (1) $L(r') \cup L(r'') \subset L(r)$, (2) $L(r) \subset L(r')$ and (3) $L(r) \subset L(r'')$. That pretty much covers it. You can separate the proof out if you want, but all the details are there... – copper.hat Nov 22 '12 at 20:15
OK I see it now, thanks alot man – DanielY Nov 22 '12 at 22:45