# 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 '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? 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 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 .

I had not the enough reputation in this community to leave a comment on @Umamg's answer; so, I try to complete Umang's answer in mine.

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.

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.

A direct diagonalization argument is very much usable here (even though a somewhat unorthodox choice, as we have "more natural" separating examples available to us).

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.

Everything in the preceeding paragraph remains true if we replace "context-free" by "context-sensitive".