The proof that L is not regular language

Question

Let $L=\{x$| the number of $0$ in $x$ is not equal to $1$} is the language on the alphabet {$0,1$}, prove that $L$ is not RL(regular language)

I am having trouble with this. It seems that pumping lemma is not useful in this question.

Answer 1

Hint: Use the relation of Nerode. Let $L$ be a language over the alphabet $\Sigma$, (here $\Sigma=\{0,1\}$).

Define the relation $\equiv_L$ as

$u\equiv_L v :\Leftrightarrow (\forall w\in\Sigma^*: uw\in L\Leftrightarrow vw\in L).$

This is an equivalence relation and so you can form the equivalence classes. If the index (=number of equivalence classes) is finite, then $L$ is regular.

Here the number of equivalence classes is infinite. For instance, $1$, $11$, $111$ and so on lie in different classes, e.g. $1\not\equiv_L 11$ since for $w=0$, we have $10\not\in L$ but $110\in L$.