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.

  • 0
    In my view, Dave Radcliffe's post already answers the question; my comment just applies it to one example.2011-08-16

3 Answers 3

6

The Kleene star * allows zero or more repetitions.

4

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

  • 0
    I'm not sure how you denote generation $f$rom a rege$x$p, but the general idea is this: (b*a*)*--> (b*a*)(b*a*) -->(eps a)(b eps)=ab.2011-08-16
2

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

  • 0
    For some basic information about writing math at this site see e.g. [here](http://meta.math.stackexchange.com/questions/5020/), [here](http://meta.stackexchange.com/a/70559/155238), [here](http://meta.math.stackexchange.com/questions/1773/) and [here](http://math.stackexchange.com/editing-help#latex).2013-02-19