= Solution
The subset construction theorem gives $\mathcal L(D)=\mathcal L(N)$. Removing inaccessible states does not alter any computation from the initial state, so
$$
\mathcal L(D')=\mathcal L(N).
$$
Every state of $D'$ is accessible by construction. It remains to separate distinct subset states $S,T$ of $D'$. Choose $q\in S\mathbin\triangle 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_*$. Part (b)(iii) implies
$$
q_*\in\widehat\Delta(q,w),
$$
so 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_*$. 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'$ are indistinguishable, and all are accessible. Therefore $D'$ is irreducible and accepts $\mathcal L(N)$.
Back to article page
