What happens if I expand b*( (ab) b* )*?

Question

I just wanted to confirm if what I have here is correct. If I expand b*((ab)b*)* are these set of strings valid? Sorry, I tried posting it in StackOverflow but that needed code and this doesn't include code. I have explained my reasoning here.

{empty string, b, bb, bab, abb, babbabb, babbbbabbbb}

My reasoning -

empty string = * = 0
b when the first kleene star = 1
bb when the first kleene star = 2
bab = b((ab)b^0)^1 
abb = b^0((ab)b)^2
babbabb = b((ab)b^1)^1 = b((ab)b)^2 = b(abb)^2 = babbabb
babbbbabbbb = b((ab)b^3)^2 = b((ab)bbb)^2 = b((abbbb)^2 = babbbbabbb

The part that confuses me the most is ((ab)b*)* so just posting it for confirmation.

Thank you!

Answer 1

As you know, the idea of the Kleene $*$ operator is to take any ($0$ or more) number of occurrences of the string in question. So your string form really has the following components:

• $b^*$ means you have any number of $b$'s (or possibly none)
• $(ab)b^*$ means you have to have $ab$ followed by any number of $b$'s
• the pattern $\left((ab)b^*\right)^*$ means the last pattern can occur any number of times.

Let's practice on the last string you posted: $babbbbabbbb$. If this fits our scheme, the leading $b$ has to be absorbed by the initial $b^*$. The remaining string can be broken down as $abbbbabbbb = ab^4ab^4 = \left(ab^4\right)^2$. Note the repeating pattern is of form $(ab)b^3$ so it fits or scheme of $(ab)b^*$, and the entire string then fits.

For example, if, instead, you would have $bab^5ab^4$, this would not since the internal pattern of $a$'s and $b$'s does not repeat...

---

UPDATE

A correction on your example of $abb = b^0((ab)b)^2$. Note that $b^0((ab)b)^2 = ((ab)b)^2 = abbabb$, so you really need $b^0((ab)b)^1$ instead. All others are correct.

Answer 2

There is a simple way to describe this language. It is the set of all words in which every $a$ is followed by a $b$. To see this, first convince yourself that $b^*(ab^*)^* = \{a, b\}^*$ and then observe that $b^*((ab)b^*)^*$ is obtained by replacing every occurrence of $a$ by $ab$.