I think I understand pumping lemma for regular and context free languages, but there is this one, which I have no idea if it is regular or context free or not context free.

$L = \{vwwx : v,w,x \in \{0,1\}^* \wedge w\neq \epsilon\}$ - I think it may be regular, because I think that this is language, which accepts set of all words with $00,11,0101,1010$ substrings. I am sure that $\{vww^Rx : v,ww,x \in \{0,1\}^* \wedge w\neq \epsilon\}$ is regular here is proof, because it is set of all strings, with $00$ or $11$ as substring, but without reversing $w$ I am not so sure. I do not understand if idea of "expanding" $v$ and $x$ in $vww^Rx$ as shown in proof (reducing language to language which accepts set of all string with $00$ or $11$ as substring) also applies to $vwwx$. What do you think ?

I would be glad if you could help me with this one.

  • $\begingroup$ About 3 here at 1.b there is PDA for similar language. So I thought this one also may be context free. $\endgroup$
    – maqo
    May 24, 2017 at 19:27
  • $\begingroup$ Also, welcome to CS Stack Exchange! And, also, what @D.W. said. :) I've learned that he's basically always right ;-) $\endgroup$
    – Ben I.
    May 24, 2017 at 19:49
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    May 24, 2017 at 19:56
  • $\begingroup$ I deleted my answer, because I am no longer sure about #2. Also, you really should fix the question. $\endgroup$
    – Ben I.
    May 24, 2017 at 20:08
  • 1
    $\begingroup$ user3407967: I assume that pumpkin lemma was the result of a "helpful" spellchecker, but it definitely gave me a chuckle. (It goes along with the old "What's yellow and equivalent to the axiom of choice?", and, for the politically minded of a certain generation, the pumpkin patch) $\endgroup$
    – rici
    May 25, 2017 at 0:53

1 Answer 1


Let's try to figure out which words are in $L$ and which aren't. If a word $w$ contains 00 or 11 then it is certainly in $L$. Otherwise, it alternates between zeroes and ones. If it contains 0101 or 1010 then it is in $L$. We are left with the words of length at most three, that is $\epsilon,1,0,10,01,101,010$. These are the only words not in $L$. Since $L$ is cofinite, it is regular.

  • $\begingroup$ So this language includes all words from $\{0,1\}^*$ except $\epsilon,1,0,10,01,101,010$ ? $\endgroup$
    – maqo
    May 24, 2017 at 21:26
  • $\begingroup$ A language doesn't accept anything. However, it seems to include all words other than those you listed. $\endgroup$ May 24, 2017 at 21:27
  • $\begingroup$ Same question, now over a three letter alphabet please:) $\endgroup$ May 25, 2017 at 3:41
  • $\begingroup$ @HendrikJan There you go: cs.stackexchange.com/a/104178/683. $\endgroup$ Feb 12, 2019 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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