Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 3 / 12F (Automata & Formal Languages)

A state $q$ is inaccessible if no word reaches it from the initial state:

States $q$ and $q^{\prime }$ are indistinguishable if no continuation can distinguish acceptance from them, that is, for every $w\in \mathbb{W}$,

The automaton is irreducible if every state is accessible and no two distinct states are indistinguishable.

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.

Define the extended transition recursively byThe automaton accepts $w$ precisely when

The subset construction produceswhereEach deterministic state records all nondeterministic states reachable after the word read so far. This construction gives $\mathcal{L}(D)=\mathcal{L}(N)$.

We induct on the length of $w$. For $w=\epsilon$, the extended transition set is $\{q\}$, and the sole witnessing sequence is $(q)$, so the claim holds.

Write a nonempty word as $w=va$. By the recursive definition,if and only if there is some $p\in \hat{\Delta }(q,v)$ with $q^{\prime }\in \Delta (p,a)$. By the induction hypothesis, the first condition on $p$ is equivalent to a witnessing sequence for $v$ from $q$ to $p$. Appending $q^{\prime }$ gives a witnessing sequence for $va$. Conversely, deleting the last state of any witnessing sequence for $va$ gives just such a state $p$ and sequence for $v$. This proves both implications.

The subset construction theorem gives $\mathcal{L}(D)=\mathcal{L}(N)$. Removing inaccessible states does not alter any computation from the initial state, so

Every state of $D^{\prime }$ is accessible by construction. It remains to separate distinct subset states $S,T$ of $D^{\prime }$. Choose $q\in S△T$, and without loss of generality take $q\in S\setminus T$. By (Br2), some word $w$ has a witnessing sequence from $q$ to the unique final state $q_{\ast }$. Part (b)(iii) impliesso the state reached from $S$ on $w$ is accepting.

If the state reached from $T$ on $w$ were also accepting, there would be some $p\in T$ with a witnessing sequence labelled $w$ from $p$ to $q_{\ast }$. But $q$ has such a sequence too, and (Br3) says that its starting state is unique. Hence $p=q$, contradicting $q\notin T$. Thus $w$ distinguishes $S$ and $T$.

No two distinct states of $D^{\prime }$ are indistinguishable, and all are accessible. Therefore $D^{\prime }$ is irreducible and accepts $\mathcal{L}(N)$.