[samatman]

Decidability is whether one can statically determine if an algorithm halts for a given input. NFAs halt for all inputs, by construction.