-2
$\begingroup$

Lets say I have just used the pumping lemma to prove a certain L language is not CFL.

If it is not CFL can I use that as a proof that it is Decidable? Or is this not enouph and I still have to provide a Turing Machine that accepts or rejects L?

Thanks

Improve this question
$\endgroup$
  • 6
    $\begingroup$ If something costs more than one dollar, can I use that as a proof that it costs less than ten dollars? $\endgroup$ – David Richerby Jul 1 '16 at 14:11
  • 1
    $\begingroup$ Why would you think that you can assume it is decidable in that case? We're more likely to be able to help you if you edit the question to explain your reasoning and your thought process. $\endgroup$ – D.W.♦ Jul 1 '16 at 14:16
  • $\begingroup$ My reasoning was that Decidability is the next "step up" from CFL, so to say. I can see now that it if is not a CFL, it could be decidable, recognizable or even non-recognizable. $\endgroup$ – Ricardo Ferreira da Silva Jul 5 '16 at 20:16
3
$\begingroup$

No undecidable language is context free, so after proving non-CFL, it could still be decidable or not. You would need to prove that separately.

Improve this answer
$\endgroup$
2
$\begingroup$

Every undecidable language is not context-free, since all context-free languages are decidable. Since there exist undecidable languages, we conclude that there exist non-context-free languages which are undecidable.

Improve this answer
$\endgroup$

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.