Let $M$ be a nondeterministic finite automaton, having $q$ states and no $\epsilon$-transitions. If there is exactly one path through $M$ of length $n$ leading to an accept state, and $x$ is the string read along that path, then we say that $A_N(x)\le q$ (the NFS complexity of $x$ is at most $q$).