= Solution
\b[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 recognizes
$$
L(D)\cap(\Sigma^*\setminus\{w\})=L(D)\setminus\{w\}.
$$
Apply the <finite automaton emptiness test> again. \b[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>.
$$
\boxed{\text{Decidable: test }L(D)\ne\varnothing\text{ and }L(D)\setminus\{w\}=\varnothing.}
$$
Back to article page
