Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

Thanks in advance

share|cite|improve this question
up vote 1 down vote accepted

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'')$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.