2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Perhaps you can convert FM of that into a regular expression. $\endgroup$ – Mr. Sigma. Dec 2 '18 at 11:14
  • $\begingroup$ 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?? $\endgroup$ – Tom Dec 2 '18 at 11:17
  • $\begingroup$ Not directly relevant, but I find it easier to write $(A^*B^*C^*)^*$ as $(A+B+C)^*$ $\endgroup$ – chi Dec 2 '18 at 11:45
2
$\begingroup$

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^*$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tom Dec 2 '18 at 12:00
  • $\begingroup$ this won't generate bbb $\endgroup$ – Mr. Sigma. Dec 2 '18 at 12:00
  • $\begingroup$ Corrected. The symmetry is, in fact, useful in understanding and verification. $\endgroup$ – John L. Dec 2 '18 at 12:10
  • $\begingroup$ Now, both solutions are correct? $\endgroup$ – Tom Dec 2 '18 at 12:21
  • $\begingroup$ 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$. $\endgroup$ – John L. Dec 2 '18 at 12:25
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.