theory of computation

Question

Give regular expression for the complement of the language given below .

L (r) = {a²ⁿb^2m+1: n ≥ 0, m ≥ 0}  (or) r =(aa)* (bb)* b
 

Answer 1

I think it's

(a+b)*(∈ + a) + (a+b)*(bb)

The first part will accept anything that ends with a or even null string which should be accepted as the minimum length string in L ={b} so for L complement it will be null.

The second part will ensure that whatever you generate should not end in odd number of b's . (Something that is not to be accepted by the complement of this language.

Comments

Your expression is accepting b, bbb which it shouldn't. In fact your expression (a+b)*(∈+a) can be broken into (a+b)*∈ which is set of all languages.

---

Okay Mandeep. I'll check it and come with a better solution. :)

---

Ayush, your RG is generating the string $ aa $ and $ bbb $, which is also generated by the given RG. so :/

---

I think this should work

(aa)^* { ∈ + a + bb + (bba + ab + ba)(a+b)^* }

Answer 2

even no of a followed by odd no of b's  so its complement will be 

odd no of a followed by even no of b 's 

(aa)*a(bb)*

we cnnot take same no of a's and same no of b'sas they occur in the above language in the question 

correct me if iam wrong

Comments

yes it will be odd no's of a followed by even number of b.