How to prove that $L=\{w\in\{0,1,2\}^*|\#_2(w)<\#_0(w)\}$ is not regular using Myhill–Nerode theorem?
$\#_2(w)$ means the number of occurrences of $2$ in $w$, same goes for $\#_0(w)$.
I thought of the following proof:
Suppose that $L$ is regular then by Myhill–Nerode theorem the number of equivalence classes for $R_L$ is finite. ($R_L$ is a relation such that $xR_Ly\iff \forall z\in \Sigma^*: xz\in L\iff yz\in L$).
Let us inspect words of type $0^i2^j, i>j$. Because there're infinitely many words in $L$ then according to pigeonhole principle some equivalence class must contain at least $2$ words. Then exist $i,j$ such that $i=j+1$ and $p,q$ such that $p=q+2$, $p>i$, $0^i2^jR_L0^p2^q$.
Then for $z=2^{j}$, $0^i2^j\notin L$ but $0^p2^q\in L$ in contradiction to Myhill–Nerode theorem.
I'm wondering if it's OK to suppose quite concrete details like $i=j+1$ and $p=q+2, p>i$?
Best Answer
Hint: The words $0^k2^l$ and $0^k1^l$ with $l<k$ cannot be in relation $R_L$, since $0^k2^l(2^{k-l})=0^k2^k\not\in L$, but $0^k 1^l 2^{k-l}\in L$ for $z=2^{k-l}$.