Paper 2, Section I, 4H4 \mathrm{H}

Automata and Formal Languages
Part II, 2017

(a) Give explicit examples, with justification, of a language over some finite alphabet Σ\Sigma which is:

(i) context-free, but not regular;

(ii) recursive, but not context-free.

(b) Give explicit examples, with justification, of a subset of N\mathbb{N} which is:

(i) recursively enumerable, but not recursive;

(ii) neither recursively enumerable, nor having recursively enumerable complement in N\mathbb{N}.