Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's.

So far, I have $(aa)^*a((b+\varepsilon)(aa)^*)^4$, but I don't think this covers all cases. For example, $abaabaaab$ should fit the criteria, but it wouldn't be in the language described by the above regular expression. Any help is appreciated!

  • 1
    $\begingroup$ The string abaabaaab has an even number of a’s and so isn’t in the language. $\endgroup$ Apr 27 at 5:12

2 Answers 2


Here is how to construct a regular expression for the set of strings over $\{a,b\}$ which contain an even number of $a$'s and at most one $b$.

Strings that contain no $b$ are of the form $a^n$, where $n$ is even. Such strings can be described using the regular expression $(aa)^*$.

Strings that contain a single $b$ are of the form $a^n b a^m$, where $n+m$ is even. Thus either $n,m$ have the same parity. The case where both are even is described using $(aa)^*b(aa)^*$, and the case where both are odd is described using $a(aa)^*ba(aa)^*$.

In total, we obtain the regular expression $$ (aa)^*(\epsilon + b(aa)^*) + a(aa)^*ba(aa)^*. $$


It says the constraints are

  1. Odd number of A's and
  2. At most 4 B's let's start the expression

->string may start with both A & B


->say the first letter of the string be A

======>we need kernels should contain even A's to make it odd

   ========>of kind(_a_a_)

->say if the expression has started with B

======>we need to include odd number of A's into the second term

 ======>A*B*(say for singular B's)

-> and to make whole recursion we will be taking whole (*).


So, the final expression that would be accepting any string that would have odd number of A's and at most 4 B's is : (A+B).(A+B+AA+BAA+ABA+AAB)*

(not simplified for understanding...)

  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. I can match AA with the expression you present as well as BBBBB. $\endgroup$
    – greybeard
    Jun 25 at 7:14
  • $\begingroup$ (I find using capital letters irritating here. The bigger slanted ones can be produced enclosing them (a ($L^AT_EX$) formula) in \$ dollar signs.) $\endgroup$
    – greybeard
    Jun 25 at 7:18

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.