Showing that the language $L$ with $\{1^n0^m |\space n \neq 2^m\}$ is not regular using Myhill-Nerode is easy: Let $i, j\in \mathbb{N}.i\neq j.$ It follows $1^{2^i}\nsim 1^{2^j}$ because $1^{2^i}0^{i}\notin L$ but $1^{2^j}0^{i}\in L$. Therefore $L$ has an infinite amount of Myhill-Nerode equivalence classes and is not regular. But how do I show this using the general version of the pumping lemma for regular languages? https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#General_version_of_pumping_lemma_for_regular_languages
-
1$\begingroup$ Well, what have you tried? $\endgroup$ – dkaeae Mar 19 '19 at 16:36
Let $p$ be the pumping length, and consider the string $u=1^{2^{p!+p}}$, $w = 0^p$, $v = \epsilon$. Notice $uwv \in L$. According to the pumping lemma, there is a value $q \in \{1,\ldots,p\}$ such that $1^{2^{p!+p}} 0^{p-q+iq} \in L$ for every $i \geq 0$. Choosing $i = 1 + p!/q$, we obtain a contradiction.
This answer uses the standard pumping lemma. Depending on your perspective, this answer may or may not have used the general pumping lemma.
Consider $L' = (1^*0^*) \setminus\{1^n0^m \mid n \neq 2^m\}=\{1^n0^m\mid n=2^m \}$.
Suppose the pumping length of $L'$ is $p$. Consider $w=1^p0^{2^p}\in L$. Then $w=xyz$, where $|xy|\le p$, $|y|\ge 1$ and $xy^0z=xz\in L'$. Since $y$ contains 1 only, $xz$ has less numbers of 1s and the same numbers of 0s as $w$. So $xz\not\in L'$. That contradiction shows $L'$ and, hence, $L$ is not regular.