0
$\begingroup$

I've been reading the decidablity and undecidability chapters in Sipser's "Intro to Theory of Computation" however I could not find an explanation on the existence of a language that is both non-context free and decidable.

The only reference to this was a simple language hierarchy diagram showing where the decidable/recognisable bounds were in relation to language types.

I'm unsure as to how I should approach this but I've thought about proving this by diagonlisation:

  • Let $M$ be the set of all decideable Turing Machines, and $L$ the set of all languages that are context-free. (Assume finite alphabet)
  • By drawing up and filling the table where each language corresponds to a Turing Machine, I was hoping that I could find a contradiction in some $m \in M$ where there is no corresponding language $l \in L$.

I know that this will not work as both $M$ and $L$ are countable.

Any ideas on how I should approach this?

$\endgroup$
  • 1
    $\begingroup$ Most decidable languages are not context-free. The classic example is a^nb^nc^n. See Wikipedia for more info: en.wikipedia.org/wiki/… $\endgroup$ – Mark VY Apr 21 '17 at 3:41
  • $\begingroup$ If the book does not equip you to answer this for yourself in 30s, throw it away. My guess is you have to read on (or more closely). $\endgroup$ – Raphael Apr 21 '17 at 5:15
  • $\begingroup$ Okay, I used very poor choice of words to describe what I was really after, rather than "explanation" I was meant to say "explicit proof". Sipser used the diagonalisation argument to show that there exists an undecideable language for $A_{TM}$ which I understood, and I wanted to try do the same, to show the existence of a decideable and non-context-free language as I remember seeing a question that asked for this using a diagonalisation proof. I should have asked this question on the diagonlisation method itself rather than under the concept of decideable context-free languages. $\endgroup$ – J Z Apr 21 '17 at 8:54
  • 1
    $\begingroup$ Possible duplicate of How to prove that a language is not context-free? $\endgroup$ – David Richerby Apr 21 '17 at 11:05
1
$\begingroup$

You could simply consider the language $L = \{a^k | k \text{ is a prime number }\}$. This is not a context free language, but surely this is recognizable by a Turing Machine that checks if the length N of the input is not divisible by any number between 2 and N-1 .

$\endgroup$
0
$\begingroup$

There are two quick answers within easy reach of undergrad courses:

  1. CFL ⊊ CSL ⊊ R
  2. CFL ⊊ P ⊊ R

Basically, "all" of complexity theory happens "between" CFL and R (with some notable exceptions). Just have a look at the complexity zoo and note how far down CFL is, and how far up R.

$\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.