I want Regular Expression for language L defined over {a,b} and L does not contain substring 'bbb'. I tried something but could not get proper answer.
$\begingroup$ $\endgroup$
2 
- 2$\begingroup$ What did you try and where did it go wrong? $\endgroup$Peter Taylor– Peter Taylor2018-03-28 07:36:45 +00:00Commented Mar 28, 2018 at 7:36
- $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$Raphael– Raphael2018-03-28 10:09:37 +00:00Commented Mar 28, 2018 at 10:09
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
We can decompose every string over $\{a,b\}$ as a sequence of runs: $$ a^{n_1} b^{n_2} a^{n_3} b^{n_4} \ldots \text{ or } b^{n_2} a^{n_3} b^{n_4} a^{n_5} \ldots, $$ where $n_1,n_2,n_3,n_4,\ldots \geq 1$. In our case the constraint is $n_2,n_4,n_6,\ldots \leq 2$.
Let us start with the identity $$ (a+b)^* = (a^+b^+)^*a^* + (b^+a^+)b^*, $$ which corresponds to the description above.
Can you think of a way to modify it so that all powers of $b$ are at most 2?
