Proving that a language is regular by giving a regular expression

Question

I am stumped by this practice problem (not for marks):

{w is an element of {a,b}* : the number of a's is even and the number of b's is even }

I can't seem to figure this one out. In this case 0 is considered even. A few acceptable strings: {}, {aa}, {bb}, {aabb}, {abab}, {bbaa}, {babaabba}, and so on

I've done similar examples where the a's must be a prefix, where the answer would be: (aa)(bb) but in this case they can be in any order.

Kleene stars (*), unions (U), intersects (&), and concatenation may be used.

Edit: Also have trouble with this one

{w is an element of {0,1}* : w = 1^r 0 1^s 0 for some r,s >= 1}

Answer 1

This is kind of ugly, but it should work:

ε U ( (aa) U (bb) U ((ab) U (ba) (ab) U (ba)) )*

For the second one:

11*011*0

Generally I would use a+ instead of aa* here.

Answer 2

Edit: Undeleted re: the comments in NullUserException's answer.

1) I personally think this one is easier to conceptualize if you first construct a DFA that can accept the strings. I haven't written it down, but off the top of my head I think you can do this with 4 states and one accept state. From there you can create an equivalent regex by removing states one at a time using an algorithm such as this one. This is possible because DFAs and regexes are provably equivalent.

2) Consider the fact that the Kleene star only applies to the nearest regular expression. Hence, if you have two individual ungrouped atoms (an atom itself is a regex!), it only applies to the second one (as in, ab* would match a single a and then any number - including 0 - b's). You can use this to your advantage in a case where you want something to exist, but you're not sure of how many there are.