0
$\begingroup$

I'm trying to get a better understanding for the relationship between decidability and a few other things so that I can get a better grasp of the topic. Any info helps!

Is every decidable language a deterministic context free language? Are there any decidable languages that are not recognizable? Is the question "Does a given PDA accept a given input?" decidable? Under what operations are decidable languages not closed?

$\endgroup$
  • $\begingroup$ Think about the language L={xx : x in {0,1}*} :) $\endgroup$ – VashTheStampede Apr 7 '18 at 6:06
  • $\begingroup$ This is four completely separate questions and needs to be posted as such. The Stack Exchange format doesn't cope well with answers to multiple questions all mixed together. Your first three questions are very basic and are covered by any textbook or set of lecture notes on formal language theory. Your fourth question is rather vague -- there are infinitely many possible operations on languages; what sort of operations are you thinking about? $\endgroup$ – David Richerby Apr 8 '18 at 15:01
4
$\begingroup$

You are asking several disparate questions:

  • Is every decidable language a deterministic context-free language? No. There are even context-free languages which are not deterministic context-free. Furthermore, membership in a context-free language (deterministic or not) can be decided in polynomial time, whereas the time hierarchy theorem shows that there are languages decidable in time $O(n^{\log n})$ (say) but not in time $O(n^{\log\log n})$, and in particular not in polynomial time.

  • Are there any decidable languages that are not recognizable? A language is decidable iff both the language and its complement are recognizable.

  • Is the question "Does a given PDA accept a given input?" decidable? Yes, though the algorithm isn't obvious. One way is to convert the PDA to an equivalent context-free grammar in Chomsky normal form, and then use the CYK algorithm.

  • Under what operations are decidable languages not closed? Decidable languages are not closed under taking prefixes. The language of pairs $M,n$ such that $M$ halts within $n$ steps is decidable. But the language of all prefixes ending with $,$ is the halting problem, which is not decidable. (I'm skipping a few steps here.)

| cite | 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.