0
$\begingroup$

This question already has an answer here:

Hey was wondering if I'm applying the pumping lemma correctly for this proof or if this proof could be improved?

Suppose $L = \{www:w\in\{0,1\}^*\}$ is a regular language. Let $p$ be the number from the Pumping Lemma. Consider $s = 0^p10^p10^p1$, since $s \in L$ the conditions of the pumping lemma must hold for $s = xyz$. Now let $x= 0^p$, $y = 1$, and $z = 0^p10^p1$. Then since $|xy|\le p$ and if we let $i = 2$ then $s’=0^p110^p10^p1$. But clearly $s’ \notin L$ which is a contradiction to the Pumping Lemma so $L$ is not regular.

$\endgroup$

marked as duplicate by David Richerby, Evil, Raphael Feb 11 at 12:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ "What's wrong with my pumping lemma proof?" is about a different language, but you've made the same mistake as that person did, so most of my answer there applies. See, in particular, the third paragraph $\endgroup$ – David Richerby Feb 11 at 13:35