Regular expression for strings with even number of a's and odd no of b's

Even-Even = (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*

(Even-Even has even number of Aas and b's both)

Even a's and odd b's = Even-Even b Even-Even

This hsould work

This regular expression takes all strings with even number of a's and even number of b's

r1=((ab+ba)(aa+bb)*(ab+ba)+(aa+bb))*

Now to get regular expression for even a's and odd b's

r2=(b+a(aa+bb)*(ab+ba))((ab+ba)(aa+bb)*(ab+ba)+(aa+bb))*

For even number of a's and b's , we have regex:

E = { (ab + ba) (aa+bb)* (ab+ba) }*

For even number of a's and odd number of b's , all we need to do is to add an extra b in the above expression E.

The required regex will be:

E = { ((ab + ba) (aa+bb)* (ab+ba))* b ((ab + ba) (aa+bb)* (ab+ba))* }

I would do as follows:

• regex even matches the symbol a, then a sequence of b's, then the symbol a again, then another sequence of b's, such that there is an even number of b's:

even -> (a (bb)* a (bb)* | a b (bb)* a b (bb)*)

• regex odd does the same with an odd total number of b's:

odd -> (a b (bb)* a (bb)* | a (bb)* a b (bb)*)

A string of even number of a's and odd number of b's either:

• starts with an odd number of b's, and is followed by an even number of odd patterns amongst even patterns;
• or starts with an even number of b's, and is followed by an odd number of odd patterns amongst even patterns.

Note that even has no incidence on the evenness/oddness of the a/b's in the string.

regex -> (

b (bb)* even* (odd even* odd)* even*

|

(bb)* even* odd even* (odd even* odd)* even*

)

Of course one can replace every occurence of even and odd in the final regex to get a single regex.

It is easy to see that a string satisfying this regex will indeed have an even number of a's (as symbol a occurs only in even and odd subregexes, and these each use exactly two a's) and an odd number of b's (first case : 1 b + even number of b's + even number of odd; second case : even number of b's + odd number of odd).

A string with an even number of a's and an odd number of b's will satisfy this regex as it starts with zero or more b's, then is followed by [one a, zero or more b's, one more a and zero or more b's], zero or more times.

The structured way to do it is to make one transition diagram and build the regular expression from it. The regex in this case will be

(a((b(aa)*b)*a+b(aa)*ab)+b((a(bb)*a)*b+a(bb)*ba))b(a(bb)*a)*

It looks complicated but it covers all possible cases that may arise.