An automaton accepting a regular language is irreducible exactly when it has the smallest possible number of states among deterministic automata accepting that language. The irreducible automaton is unique up to isomorphism; its states correspond to the Myhill--Nerode equivalence classes.


Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 3 / 12F / a / iv / Solution

 Solution (source code)