Thursday, March 22, 2012

Prove the language L ={w | w belongs to (0+1)^*, where w contains equal number of a's and b's} is not regular

Prove the language L1 ={w | w , where w contains equal number of a's and b's} is not regular

Proof :

Let,
Language L2 = 0^*1^* --------------- A
Language L3 = {0^n1^n | n>=0} --------- B

L1∩L2 = L3 --------------- C

hence, from A we know that L1 is regular
then L3 is also regular. This produces contradiction. hence L1 must not be regular.


result : Language where w contains equals number of a's and b's is not regular
see Pumping Lemma For regular Language

No comments: