# Show $\{1^n0^m |\space n \neq 2^m\}$ not regular using pumping lemma

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

• Well, what have you tried? – dkaeae Mar 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.
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.