I tried doing this, but kept failing to prove. I know how to prove that the language is nonregular when n0(w) = n1(w). The following is the proof for n0(w) = n1(w) using pumping lemma:

Assume L is regular. Then, by the Pumping Lemma, there is a natural number m such
that any w ∈ L with |w| ≥ m can be factored as w = xyz with |xy| ≤ m and |y| > 0,
and xyi
z ∈ L, for i = 0, 1...
Pick w = 0^m 1^m.
Then, 0^m 1^m = xyz, where y = 0k, for k > 0.
By the Pumping Lemma, xz ∈ L.
But, n0(xz) does not equal n1(xz).
The assumption that L is regular thus is false.
Hence Proved

However, I don't know how to prove it for when number of 0 is not equal to number of 1.


Hint. You probably know that regular languages are closed under complement. Now, what is the complement of your language?

  • $\begingroup$ I want to use pumping lemma for this proof :) $\endgroup$ – WOW Sep 21 '17 at 10:06
  • $\begingroup$ Why do you insist to use the pumping lemma? The pumping lemma does not characterize regular languages. In other words, there are some nonregular languages that satisfy the pumping lemma. $\endgroup$ – J.-E. Pin Sep 22 '17 at 8:24
  • $\begingroup$ Because I want to learn it and it is giving me a very hard time. I can prove some questions, but I get stuck on others. $\endgroup$ – WOW Sep 22 '17 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.