Regular expression for complement of L

Question

Given the language $L((aa)^{*}(bb)^{*}b)$ what is the regular Expression for complement of L.

a)$(a+b)^{*}ba(a+b)^{*} + a(aa)^{*}b^{*} + a^{*}(bb)^{*} + \epsilon$

b)$(a+b)^{*}ba(a+b)^{*} + (aa)^{*}b^{*} + a^{*}(bb)^{*} + \epsilon$

c)$(a+b)^{*}ba(a+b)^{*} + a(aa)^{*}b^{*} + (bb)^{*} + \epsilon$

d) None of these

Answer 1

First of all we have to understand what the language does the given regular expression generate . 

Given regular expression  :  (aa)* (bb)* b   which means this language generates : 

Even number of a's followed by odd number of b's . 

So given the language description , we can think about the complementary language easily . So there are few types of strings which will be generated by the complementary language L' . Lets mention them and write their equivalent regular expression one by one :

a) One violation of order of a's and b's i.e. at least one occurence of 'b' before 'a'   :   (a+b)* ba (a+b)*

b) Invalidating even number of a's while preserving order i.e. odd number of a's followed by any number of b's :  a(aa)* b*

c) Invalidating odd number of b's while preserving order i.e. any number of a's followed by even number of b's :  a* (bb)*

d) Besides , the null string "epsilon" is not covered by the language L  . Hence it will be part of L' as well.

Hence the overall regular expression of L' will be :   (a+b)* ba (a+b)*  +  a(aa)* b*  +   a* (bb)*   + ϵ

Hence  A) should be the correct option .