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

For a deterministic finite automaton the extended transition function of a deterministic finite automaton is recursivelyThe accepted language isFor a nondeterministic finite automaton, $\hat{\delta }(q,w)$ is the set of all states reachable from $q$ while reading $w$; recursively,Thus

The powerset construction has state set $\mathcal{P}(Q)$, initial state $\{q_0\}$, transitionand accepting states $\{S\subseteq Q:S\cap F\ne \varnothing \}$. Induction on $|w|$ givesso the two automata accept exactly the same language. If $|Q|=m$ and $F$ has one state, exactly $2^{m-1}$ of the $2^m$ subset states contain it and are accepting, including states that may be unreachable.