# prove that l={w ∈ {0, 1}*: n0(w) ≠ n1(w)} is a non regular language?

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.

• – Shaun Sep 18 '17 at 17:21
• You can prove it with the pumping lemma and $0^{m!}1^{2m!}$ – Hagen von Eitzen Sep 18 '17 at 18:54

## 1 Answer

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

• I want to use pumping lemma for this proof :) – WOW Sep 21 '17 at 10:06
• 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. – J.-E. Pin Sep 22 '17 at 8:24
• 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. – WOW Sep 22 '17 at 16:13