Construct a regular expression

154 Views Asked by At

The problem asks me to construct a regular expression for the set of strings in $\{a,b\}^*$ that have even number of $a$ and $b$.

What I have tried is $(aa)^* + (bb)^* + (aabb)^*$ but I believe it does not cover a string like $abbbaaba$.

Many thanks,

1

There are 1 best solutions below

1
On

If you have access to a complement operator $-$, we can implement Daniel Schepler's suggestion:

$$-(-(b^* ab^* ab^*)^* + -(a^* ba^* ba^*)^*).$$

Each interior parentheses says to look for two $a$'s which are separated by (any number of) $b$'s or vice versa. By putting the stars around these you allow yourself as many pairs as you want. The minus signs can be eliminated using De Morgan's Laws if you have access to an AND operator.