Let $$L=\left\{0^n 1^{2n} \mid n > 1\right\}.$$ Show that $L$ is not regular.


If the language is regular, it must satisfy the Pumping lemma. $P$ will be our pumping length and our string $w = 0^p 1^p 1^p$. $x$ and $y$ must only contain zeroes because the length of $xy$ is less than or equal to $p$. Since the length of $y$ is greater than $0$, it must also contain some zeroes. However, if the string $xyz$ was balanced in the langauge, $xyyz$ will unbalance it by introducing additonal zeroes. Pumping lemma is a necessary property of regular languages, and one of its conditions state that for $w = xyz$, $xyyz$ must hold. Because $xyyz$ does not satisfy the language’s definition, this language is not regular.

Is this solution correct?

  • $\begingroup$ This is correct, you could probably be a little more concise on the ending. Just say that the fact that $xyyz$ is not in the language means the language does not satisfy the pumping lemma. So our assumption that the language is regular must be incorrect. It also couldn't hurt to write out $xyyz$ to be more explicit, that is, $xyyz = 0^{p+k}1^p 1^p$ for some $k \geq 1$, noting that $2(p+k) > 2p$. $\endgroup$ – cemulate Oct 19 '15 at 22:58
  • $\begingroup$ This is correct. in terms of presentation, one improvement would be to introduce $x$ and $y$ properly, by explicitly saying that $w = xyz$ is the decomposition of $w$ given by the pumping lemma, where $|xy| \le p$, $y \neq \varepsilon$ and all $x y^i z$ are in $L$. $\endgroup$ – BrianO Oct 19 '15 at 23:09

Your Answer

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

Browse other questions tagged or ask your own question.