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

Question

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!

Answer 1

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

Answer 2

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

======>(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_)
            ======>(AA)*;(BAA)*;(ABA)*;(AAB)*

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

======>((AB)+(AA)+(BAA)+(ABA)+(AAB))*

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