Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 3 / 4F / Solution

A regular expression is built from $\varnothing$, $ϵ$, and alphabet symbols using union, concatenation, and Kleene star; its language is defined by applying the corresponding set operations recursively. A deterministic finite automaton is a tuple $(Q,\Sigma ,\delta ,q_0,F)$ and acceptsKleene theorem says that the languages denoted by regular expressions are exactly those accepted by finite automata.

Regular languages are closed under finite union, using a product automaton or nondeterministic choice, and under finite intersection, using the product automaton with accepting set $F_L\times F_M$.

They are not closed under countable unions or intersections. Every language over a finite alphabet is a countable union of singleton languages, each regular, so a nonregular language such as $\{a^n{b}^n:n\ge 0\}$ is a counterexample. It is alsoa countable intersection of regular languages, giving the second counterexample.

Solved by gpt-5.6-sol high.