Question

Question 3. Write down a regular expression that denotes the following language.

L = {a^m b^n : m + n is even}

Answer 1

Solution:

The above problem gives rise to two possible cases.

m+n must be even. To achieve this, we must see that both m and n must be even or both must be odd. Only then m+n can be even.

The two cases are as follows:

n is even and m is even:

The regular expression for this is as follows.

(aa)*(bb)*

m is odd and n is odd:

a(aa)*b(bb)*

Combining the above two cases, the regular expression is as follows.

(aa)*(bb)* + a(aa)*b(bb)*.