The number of states of local automata A deterministic automaton $\mathcal A = (X, Q, q_0, F, \delta)$ is called $k$-local  for $k &gt; 0$ if for every $w \in X^k$ the set $\{ \delta(q,w) : q \in Q \}$ contains at most one element. Intuitively that means if a word $w$ of length $k$ leads to a state, then this state is unique, or said differently from an arbitrary word of length $&gt; k$ the last $k$ symbols determine the state it leads to.

Now if an automaton is $k$-local, then it need not be $k'$-local for some $k' &lt; k$, but it has to be $k'$-local for $k' &gt; k$ cause the last symbols of some word $|w| &gt; k$ determine the state, if any, uniquely.

Now I try to connect the number of states and the $k$-localness of an automaton. I conjecture:


  Lemma: Let $\mathcal A = (X,Q,q_0,F,\delta)$ be $k$-local, if $|Q| &lt; k$ then the automaton is also $|Q|$-local.


But I failed to proof, any suggestions or ideas?

I hope by this Lemma to derive something about the number of states of an automaton which is not $k$-local for all $k \le N$ given a fixed $N &gt; 0$, but $k$-local for some $k &gt; N$.
A late answer, but the bound on synchronization delay has been studied for several classes of automata: see for instance Unambiguous Automata; Béal et al. MCS'08.

In particular; there is a family of deterministic automata that have delay $\Omega(|Q|^2)$ as showed in On the Bound of the Synchronization Delay of a Local Automaton; Béal et al. TCS'98, which matches a corresponding $O(|Q|^2)$ upper bound.

P.S. the synchronization delay defined in the paper is the minimal $k$ for which the deterministic local automaton is $k$-local.