REGEX L(r) = {a^n b^m : n + m is even}, r =?

Question

So I did a problem earlier that said:

L(r) = {w in {a,b}* : w contains at least 2 a's}

For that one I said {a^2n , b} because that guarantees a string like aab or aabaab etc. Not sure how to approach the one I posted about in the title. Possibly a solution might be a^2n, b^2m so its always even, but also 2 odd numbers like a^n b^3m is also always even. Am i allowed to set boundaries like n>=m?

Thank you!

Answer 1

You correctly observe that n and m must either be both even or both odd. It only needs to be added that an odd number is one more than an even number.

A simple regular expression for "an even number of as" ( {a2n : n ≥ 0}) is (aa)*, while "an odd number of as" is (aa)*a.

Building on that, we can two cases for the original question: (aa)*(bb)* and (aa)*a(bb)*b, which can be combined into (aa)*(ab+ε)(bb)*. (Assuming you are using + for alternation and ε for the empty string.)

Answer 2

r=((a+b)^2)* ,i think this regular expression is also giving the right answer