2
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ $(b^*a^*)^* \to (b^*a^*)(b^*a^*) \to (\epsilon a)(bbb \epsilon) \to abbb$. $\endgroup$
    – user856
    Commented Aug 16, 2011 at 14:50
  • $\begingroup$ @Rahul Narain: Grea thanks ;)! Would you mind writing it as an answer so that I can accept it. $\endgroup$
    – roxrook
    Commented Aug 16, 2011 at 14:52
  • $\begingroup$ In my view, Dave Radcliffe's post already answers the question; my comment just applies it to one example. $\endgroup$
    – user856
    Commented Aug 16, 2011 at 14:55

3 Answers 3

Reset to default
6
$\begingroup$

The Kleene star * allows zero or more repetitions.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – roxrook
    Commented Aug 16, 2011 at 14:43
  • $\begingroup$ 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. $\endgroup$
    – Gadi A
    Commented Aug 16, 2011 at 15:07
2
$\begingroup$

$$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)^+$

$\endgroup$
1
  • $\begingroup$ For some basic information about writing math at this site see e.g. here, here, here and here. $\endgroup$
    – Julian Kuelshammer
    Commented Feb 19, 2013 at 13:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .