0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Well, what have you tried? $\endgroup$ – dkaeae Mar 19 at 16:36
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.