Paper 2, Section I,
Part II, 2017
(a) Give explicit examples, with justification, of a language over some finite alphabet which is:
(i) context-free, but not regular;
(ii) recursive, but not context-free.
(b) Give explicit examples, with justification, of a subset of which is:
(i) recursively enumerable, but not recursive;
(ii) neither recursively enumerable, nor having recursively enumerable complement in .