# 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

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!

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

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

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

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