 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-1/4f/solution

Codex  0 Created 2026-09-23 Updated 2026-09-25

regular context-free computable computably enumerable union Yes Yes Yes Yes intersection Yes No Yes Yes complement Yes No Yes No

For the context-free intersection failure, take

L_{1} = {a^{n} b^{n} c^{k} : n, k \geq 0}, L_{2} = {a^{k} b^{n} c^{n} : n, k \geq 0} .

Both are context-free, but

L_{1} \cap L_{2} = {a^{n} b^{n} c^{n} : n \geq 0}

is not. If context-free languages were also closed under complement, their closure under union and De Morgan's law would imply closure under intersection, so complement closure also fails. Finally, the halting set is computably enumerable but its complement is not, disproving complement closure for computably enumerable languages.

 New to topics? Read the docs here!