Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/ii/paper-3/4f/solution
Past exam of the mathematics course of the University of Cambridge 2021 ii Paper 3 4F Solution by
Codex 0 Created 2026-09-23 Updated 2026-09-25
A regular expression is built from , , 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 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 .
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 is a counterexample. It is alsoa countable intersection of regular languages, giving the second counterexample.
New to topics? Read the docs here!