# Language of all strings that has exactly 1 triple b

I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.

Suppose we have a language L, Language of all strings that has exactly 1 triple “b” defined over alphabet set Σ = {a, b}
Now after several tries, I came up with this (a* (ab)* (ba)* )* bbb (a* (ab)* (ba)* )* but then I realize that this is wrong too because the string abbbabababb doesn't fit on this.

Kindly someone point out at my mistake or help me solve it as I have spent almost an hour on this.

• Perhaps you can convert FM of that into a regular expression. – Mr. Sigma. Dec 2 '18 at 11:14
• I don't have or know the FA of this. I am trying to convert it directly into RE. @Mr.Sigma. You got any ideas?? – Tom Dec 2 '18 at 11:17
• Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$ – chi Dec 2 '18 at 11:45

To be clearer, we use "triple $$b$$'s" to mean three consecutive $$b$$'s.

What you would like to figure out first is a detailed description or characterization of a string that has not triple $$b$$'s and that does not end at an $$b$$, the part of the string that is before that triple $$b$$.

That string should start with zero or more $$a$$'s, possibly followed by one or two $$b$$'s followed by one or more $$a$$'s, possibly followed by one or two $$b$$'s followed by one or more $$a$$'s, and so on for some rounds. That is, $$a^*((b\mid bb)aa^*)^*$$.

So, a regular expression could be $$a^*((b\mid bb)aa^*)^*bbb(aa^*(b\mid bb))^*a^*$$, or written symmetrically, $$a^*((b\mid bb)aa^*)^*bbb(a^*a(bb\mid b))^*a^*$$.

• Wow, you explained it really well. And I guess your answer is correct. But the answer posted above you is somewhat different and also seems to be correct. So I guess both of you are right? – Tom Dec 2 '18 at 12:00
• this won't generate bbb – Mr. Sigma. Dec 2 '18 at 12:00
• Corrected. The symmetry is, in fact, useful in understanding and verification. – John L. Dec 2 '18 at 12:10
• Now, both solutions are correct? – Tom Dec 2 '18 at 12:21
• Yes. Sigma's answer, $(a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$, can be rephrased as some rounds of strings that does not end with $b$, followed by $bbb$, followed by some rounds of strings that does not starts with $b$. – John L. Dec 2 '18 at 12:25

It seems you are almost there. You just need to care substrings with $$abb$$. One possible way is $$R.E = (a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$$

Note that I came upon this regular expression from the $$FM$$ of language you described. So, another way to find $$R.E$$ is from $$FM$$ directly.