A language $L$ is in NP if and only if there exist polynomial $q$, and a deterministic polynomial Turing machine $M$ such that, for all $x\in L$, there is a string $y$ such that $|y|\leq q(|x|)$ and $M(x,y) = 1$.My question is is it possible to exchange $M$ for a finite automaton?Thank you
NP and finite automata
complexity theory;np