Let $\Sigma_k = \{0,1,...,k\}$ and let $NPA_{k}$ be the set of words that do not contain a palindrom (of length $\ge 2$) as a subword. How many states (minimally) must have an automaton that recognizes the language $NPA_{99}$?
I drew the automaton for $NPA_{2}$ and I proved that it must be minimally $10$ states (including the initial state and the sink state).
My question is about $NPA_{99}$. How many states (minimally) are needed to recognize this language? Personally, I think that it is also $10$. To my eye it is sufficient to remember only the two last symbols. It is because of the fact that if a word is a palindrom then it exists a subword of length $2$ or $3$ which is a palindrom.
(Pay your attention that in this case, a palindrom is a word that has $\ge 2$ symbols).
What about my solution ?