Finite automaton emptiness test
= Finite automaton emptiness test
A <finite-state automaton> recognizes a nonempty <formal language> exactly when some accepting <automaton state> is reachable from an initial <automaton state>. <Reachability in a graph> decides this in a finite transition graph. For an <Epsilon-NFA>, include its <epsilon transitions>; the non-epsilon labels of a successful <graph path> give an accepted <word>.