# Regular Expression representing the following language

I am having trouble understanding how to write a regular expression for the set of words that contain at least two b's and at least two a's, where the alphabet is {a,b}.

I understand that set of words that contain at least two b's is: [1] (a+b)*b(a+b)*b(a+b)* and the set of words that contain at least two a's is: [2] (a+b)*a(a+b)*a(a+b)*. In addition, I understand that the set of words that contain at least one a and at least one b is: [3] (a+b)*(ab+ba)(a+b)* (or at least I think that is correct).

I know the easy solution would be to use an intersection between [1] and [2]; however, I would like to understand how to accomplish this without using an intersection.

I know I would need to have (a+b)* at the beginning and at the end to say that any string made up of a's and b's can be at the beginning and at the end. But I am having trouble understanding the logic between those two points.

Just looking for some direction as I do not know where to go from there.

You have written (a+b)(ab+ba)(a+b)

This contains atleast 1 a & at least 1 b. So what are ab & ba ? ab & ba are permutations of string you can form with at least one a & at least one b ! As you are asking for hint, You can write something like (a+b)* (All Permutations of aabb ) (a+b)*

Hope this helps.

There are just 6 permutations (4!/2!2!) of aabb here, so it wont be hard to calcualate them ! .

• Figured it might be just writing all possible permutations but wasn't sure if there was another approach. Thanks! – E. Otero Dec 10 '15 at 4:22

Random junk is $(a \mid b)^*$, then (at least) two $b$ is $(a \mid b)^* b (a \mid b)^* b (a \mid b)^*$. ($b$s separated by junk). Two $a$, two $b$ is one of $aabb$, $abab$, $abba$, $baba$, $bbaa$, $baab$ (this checks, there must be $\binom{4}{2} = 6$ of them). Fill out with junk:

$$(a \mid b)^* a (a \mid b)^* a (a \mid b)^* b (a \mid b)^* b (a \mid b)^* \mid \dotsb$$

(fill out all the 6 alternatives above with $(a \mid b)^*$ between fixed symbols, alternate between them).

Yes, very ugly, but easy to see it does the job.