My friend is also in CSE355 and doesnt like the pumping lemm

My friend is also in CSE355 and doesn\'t like the pumping lemma, but is still convinced that there are in fact nonregular languages. He is convinced that L = {w {0, 1}*: w is not of the form 0^n 1^n} is non-regular in that it is the complement of the non-regular language L\' = [0^n 1^n: n greaterthanorequalto 0}. Is my friend correct? He is not correct because L is not actually the complement of L\'. He is not correct because non-regular languages are not closed under complement, so L may or may not be regular (i.e., the proof doesn\'t establish anything about L.) He is correct because we showed that regular languages are closed under complement, so there is no possibility that L could be regular, given that L\' is non-regular. He is correct because for any DFA to recognize L, the DFA would have to count and check that the number of 0\'s and 1\'s are different. He is right because anyone who does not like the pumping lemma must be right.

Solution

C option is correct. He is correct because we already know that regular languages are closed under complement and same applies for non regular languagaes and we also know that if a language is non regular then there is not a single DFA which will recognize the language L or L\'.