Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
2  
$(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

 
discard

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.