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

Are the languages generated by the regular expressions $(a + b)^*$ and $(b^*a^*)^*$ the same language?

The solution for this problem is yes, but I couldn't figure out why it is true. The first regular expression $(a + b)^*$ generate all strings over alphabet $\{a, b\}$, it makes sense to me. On the other hand, how does the second regular expression generate, say, the string $abbb$? From my understanding, the order of the concatenation of $b$ and $a$ does affect the result of *. Any idea? Thank you.

share|cite|improve this question
$(b^*a^*)^* \to (b^*a^*)(b^*a^*) \to (\epsilon a)(bbb \epsilon) \to abbb$. – Rahul Aug 16 '11 at 14:50
@Rahul Narain: Grea thanks ;)! Would you mind writing it as an answer so that I can accept it. – Chan Aug 16 '11 at 14:52
In my view, Dave Radcliffe's post already answers the question; my comment just applies it to one example. – Rahul Aug 16 '11 at 14:55
up vote 5 down vote accepted

The Kleene star * allows zero or more repetitions.

share|cite|improve this answer

Simple enough - remember that $b^*=\{\varepsilon, b, bb,\dots\}$ so you can think of this as $(b^* a^*)^* =((b^* )+(a^* ))^*$

share|cite|improve this answer
I still don't get it. Your interpretation make me feel like the concatenation is actually the union. It would be great if you can generate the string $abbb$ from that regular expression. Thank you. – Chan Aug 16 '11 at 14:43
I'm not sure how you denote generation from a regexp, but the general idea is this: (ba)*--> (ba)(ba) -->(eps a)(b eps)=ab. – Gadi A Aug 16 '11 at 15:07

$$b^* = \{\varepsilon,b,bb,\ldots\}$$ $$a^*=\{\varepsilon,a,aa,\ldots\}$$ we have to prove $(b^*a^*)^* = (b + a)^*$ and we know $b+a=a+b$

$b^*a^*=a^*$ if we take $b^*=\varepsilon$ string can start with $a$ u can see or $\varepsilon$

$b^*a^*=ba^*$ if we take $b^*=b$ string can start with $b$ u can see

$b^*a^*=ba^*$ if we take $b^*=bb$ string can start with $bb$ ucan see and so on $b^*a^*=bbbbbb.....a^*$ and if do the same thing with a then

$b^*a^*=b^*$ if $a^*=\varepsilon$ can ends with $b$ and $\varepsilon$ $b^*a^*=b^*a$ if $a^*=a$ can ends with $a$ and so on b$^*a^*=b^*.aaaaaaaaaa......$ $(b^*a^*)^*=(b^*a^*).(b^*a^*)$ now we have $(b^*a^*)^*$ we can say any string starts with $\varepsilon$ or $a$ or $b$ and ends with $\varepsilon$ or $a$ or $b$

and have any combination of $a$ or $b$ or both

so we can say that $(b^*a^*)^*=(b+a)^*$ or $(a+b)^*$

or go with this

now $b^*$ has $\varepsilon$ thats why when concatnated with $a^*$ ,$a$ can come first means if we take one value from $b^*$ which is $\varepsilon$ then $(\varepsilon.a^*)^*=(a^*)^* .......1$ and if we take $a^*=\varepsilon$ then

$(b^*\varepsilon)^*=(b^*)^* ........2$

and $(a^*)^*=a^*.a^*=a^*.(a+\varepsilon)^+$ ...from $1$ and $a^*=(a+\varepsilon)^+$

share|cite|improve this answer
For some basic information about writing math at this site see e.g. here, here, here and here. – Julian Kuelshammer Feb 19 '13 at 13:20

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.