Search code examples
regexregular-language

Proving that a language is regular by giving a regular expression

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}

Solution

  • 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.