Take the 2-minute tour ×

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|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
add comment

3 Answers

up vote 5 down vote accepted

The Kleene star * allows zero or more repetitions.

share|improve this answer
add comment

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

share|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: (b*a*)*--> (b*a*)(b*a*) -->(eps a)(b eps)=ab. –  Gadi A Aug 16 '11 at 15:07
add comment

$$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|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
add comment

Your Answer


