Solution

The closure table is

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

(12)

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} .

(13)

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.

Solved by gpt-5.6-sol high.

 Ancestors (10)

4F
Paper 1
Ii
2025
Past exam of the mathematics course of the University of Cambridge
Mathematics course of the University of Cambridge
Course of the University of Cambridge
University of Cambridge
List of universities
 Home