Example of a recursively enumerable language that is not context free

Question

What is a simple example of a recursively enumerable language that is not context free? My textbook is awful in providing such an example explicitly.

To be clear this isn't a hmk question.

Answer 1

The class of recursively-enumerable is very broad indeed. It includes any language for which there is a Turing machine which will halt and accept any string in the language (without requiring that the Turing machine halt if given a string not in the language). So an example of a recursively-enumerable language is the set H of descriptions (in some formalism) of Turing machines which halt on a given input. Since a there is a Turing machine which simulates any Turing machine (the so-called Universal Turing Machine), valid strings in H can certainly be recognized, but the undecidability of the Halting Problem shows that H is not recursive.

Any Turing machine can be represented as an unrestricted formal grammar (and consequently a formal grammar is a description of a Turing machine). (The actual construction is tedious if not herculean and I don't suggest trying it.) So any Turing machine for which the halting problem is undecidable defines a recursively-enumerable language which is not context-free (or even context-sensitive).

On a more pedantic level, examples of context-sensitive languages which are not context-free include:

{ ap | p is prime }
{ anbncn | n ≥ 0 }
{ α | α ∈ {a, b, c}* ∩ #a(α) = #b(α) ∩ #b(α) = #c(α) }

(In the last one, #x(α) is the number of occurrences of x in α. In other words, it's the set of strings containing the same number of as, bs and cs.)