Let M $=$def $($Q$,,,$q$0,$F$)$ be an fa $($nfa or dfa$)$ and letn $=$def $|$Q$|.$ The regular language accepted by M is non$-$empty if and only if it accepts a string of length at most n $1.$