Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3 / d / i

The problem is decidable. We need exactly one accepted word, even if that word has several accepting runs in the nondeterministic finite automaton.

First convert the input nondeterministic finite automaton to an equivalent deterministic finite automaton $D$ using the subset construction, taking epsilon closure where necessary. In the finite transition directed graph of $D$, test whether an accepting automaton state is reachable from the initial automaton state. This is the standard finite automaton emptiness test. If none is reachable, the recognized formal language is empty, so answer no.

Otherwise retain a graph path to an accepting automaton state and read its labels to obtain one accepted word $w$. If the initial automaton state is accepting, $w$ may be the empty word. Build a complete deterministic finite automaton for the singleton formal language $\{w\}$: it tracks the matching prefix of $w$, accepts only after exactly its full length, and enters a rejecting sink on a mismatch or any extra input symbol.

Complement that complete deterministic finite automaton by exchanging accepting and rejecting automaton states. Form its product with $D$, accepting exactly when the $D$ coordinate accepts and the other coordinate accepts. This product recognizesApply the finite automaton emptiness test again. Answer yes if and only if this difference is empty. The first test guarantees that $w$ belongs to $L(D)$; the second guarantees there is no different accepted word. All constructions have finitely many automaton states and all reachability tests terminate. This gives a singleton-language test for finite automata.