Prove that the class of Turing decidable languages is strictly larger than the class of context free languages. (Give a language that is Turing decidable, but which violates the pumping lemma for context free languages).

I don't know how to solve this. Please help


HINT: Can you think of a set $A$ of finite strings which is

  • Easy to describe (this is informal, but it's better to start informally than to look for something which you know fits the definition of "decidable" - in practice, most things which are "easily describable" will be decidable), but

  • Doesn't satisfy the pumping lemma?

In fact, probably any example you've seen of a set of strings not satisfying the pumping lemma is Turing decidable . . .

  • $\begingroup$ Sorry, I'm pretty new to this. I don't even know where to start. $\endgroup$ – Brice Petty Nov 21 '15 at 1:31
  • $\begingroup$ @BricePetty Have you had any exercises of the form "Show that --- is not a CFL by showing it fails the pumping lemma?" $\endgroup$ – Noah Schweber Nov 21 '15 at 1:37
  • $\begingroup$ yes, I have. I just don't understand the connection $\endgroup$ – Brice Petty Nov 21 '15 at 2:58
  • $\begingroup$ @BricePetty OK, so take your favorite example of a language L which is not a CFL, since it fails the pumping lemma. If you can show L is Turing decidable, then you're done. $\endgroup$ – Noah Schweber Nov 21 '15 at 3:01
  • $\begingroup$ Okay, I have chosen the language L = even length binary string where the first half of the string is the same sequence as he second half of the string. By pumping lemma, I have proven that this language is not a CFL. Now, how would I go about showing this string is turing decidable? $\endgroup$ – Brice Petty Nov 21 '15 at 4:16

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.