# 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/… Apr 21, 2017 at 3:41
• Apr 21, 2017 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). Apr 21, 2017 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, 2017 at 8:54
• Possible duplicate of How to prove that a language is not context-free? Apr 21, 2017 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 decidable by a Turing Machine that checks if the length N of the input is not divisible by any number between 2 and N-1 .

One way to show that the language $$L=\{a^p: \text{p is a prime number}\}$$ is not context-free is to use pumping lemma for CFLs in the following way:

If $$L$$ was a CFL, then given an arbitrary long string in this language, say $$a^p$$ with $$p$$ being greater than the pumping length of $$L$$, this string would be decomposed into five parts $$uvxyz$$ with $$|vy|\geq 1$$ and so that for any $$i\geq 0$$ the string $$uv^ixy^iz$$ would belong to $$L$$.

Let $$l:=|vy|$$, then the above discussion shows that all the following strings are part of the language $$L$$: $$a^p, a^{p+l}, a^{p+2l}, \ldots, a^{p+nl}, \ldots$$

That is, the set of prime numbers contains an infinite arithmetic progression which is impossible since the number $$p+pl$$ is divisible by p.

We can construct in a straight-forward way a notation system for context-free grammars, which then lifts to a notation system $$(L_w)_{w \in \Sigma^*}$$ for the context-free languages. We can then define the diagonal language $$L_\Delta = \{w \in \Sigma^* \mid w \notin L_w\}$$. The usual proofs that each context-free language is decidable are all uniform in the grammar, and thus give us that $$L_\Delta$$ is decidable. By construction, $$L_\Delta$$ is not context-free.