# Existence of non-context free but decidable languages

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?

• Most decidable languages are not context-free. The classic example is a^nb^nc^n. See Wikipedia for more info: en.wikipedia.org/wiki/… – Mark VY Apr 21 '17 at 3:41
• – Raphael Apr 21 '17 at 5:11
• 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). – Raphael Apr 21 '17 at 5:15
• 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. – J Z Apr 21 '17 at 8:54
• Possible duplicate of How to prove that a language is not context-free? – David Richerby Apr 21 '17 at 11:05

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 .

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.