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 '17 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 '17 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 '17 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 '17 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 '17 at 0:53

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 '17 at 21:26
  • $\begingroup$ A language doesn't accept anything. However, it seems to include all words other than those you listed. $\endgroup$ – Yuval Filmus May 24 '17 at 21:27
  • $\begingroup$ Same question, now over a three letter alphabet please:) $\endgroup$ – Hendrik Jan May 25 '17 at 3:41
  • $\begingroup$ @HendrikJan There you go: cs.stackexchange.com/a/104178/683. $\endgroup$ – Yuval Filmus Feb 12 at 7:02

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.