-1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

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

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.

$\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.