Formal Languages - Regular Expression

Question

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 "truth tables" inputs over it and it seems ok. But the moment I add the requirement, things go haywire. Mostly because when pushing in those "b"s, you can suddenly use the OR to break things up.

Same thing on the second one....

Any help would be greatly appreciated!

Norah

Answer 1

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

1. bbb*(a+b)*a*
2. bb*(a+b)(a+b)*a*
3. b*(a+b)(a+b)(a+b)*a*

Answer 2

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