Formal Languages - Regular Expression I've been battling the following two questions for more than a day today.

Write a regular expression (comprised of {a, b}) that contain at least two b and do not contain abb.
Write a regular expression (comprised of {a, b}) that contain abba and do not contain baa.

For the first part I wrote a basic one to start off with that doesn't handle the must two-b:
b* OR a* OR (a+ AND b)* OR a*

I ran a few &quot;truth tables&quot; inputs over it and it seems ok. But the moment I add the requirement, things go haywire. Mostly because when pushing in those &quot;b&quot;s, you can suddenly use the OR to break things up.
Same thing on the second one....
Any help would be greatly appreciated!
Norah
For the first language
$$
b^2b^*(1+a) + (ba + aa^*ba)a^*b(1 + a)
$$ 
For the second language
$$
(aa^*b + bb^*ab)(ab + bbb^*ab)^*ba(bb^*a)^*
$$
You have b*(a+b)*a* that matches words without abb.

Split the string on its first a. On the left it will have b* and on the right it will have (a+b)*a*. The two b can be both on left, one on left and one on right or both on right side. That's three cases. In each case two things of the form x* have to turn into xx*.


bbb*(a+b)*a*
bb*(a+b)(a+b)*a*
b*(a+b)(a+b)(a+b)*a*