Let be $k\ge1\in \mathbb{N}$. Is there a deterministic automata graph that recognizes the language $L_k=\{w|w \mbox{ contains an a within the k last chars}\}$ ? The alphabet is $\{a,b\}$.
Reformulation : the question like is : How to construct an automata that does $L_k=\Sigma^*(\Sigma^k\mbox\ b^k)$. (I'm not sure, does it contains an a at the spcific position k or within the k last chars ?).
I know how to do it for a specific $k$, but how to do it for any $k$ ?
My attempt from Brian Tung's idea
I created two states to begin with : a state where there has been at least $k$ characters since last $a$ and a state where there's been fewer than $k$ characters since last $a$ :
I tried then to do it for $k=1$ and $k=2$.
But I don't know how to generalize...
General approach. Have a set of states that keeps track of two quantities: (i) how many characters have been ingested in a row without an $a$, and (ii) how many characters are needed to reach at least $k$ characters for the string. The initial state has (i) equal to $0$ and (ii) equal to $k$, and accepting states are those where (i) is less than $k$, and (ii) is equal to $0$.
Thus, for instance, for $k = 3$, the state $(1, 2)$ would indicate that the automaton has ingested one character without seeing an $a$, and that two more characters still have to be ingested to reach the minimum of $k = 3$ characters for the string. This state could only be reached (for $k = 3$) after the string "$b$".
We move from state to state, either incrementing the number of characters seen without an $a$, or resetting it to zero; and decrementing the number of characters needed to reach a minimum of $k$. Overall, for example, for $k = 3$, we have
All leftward transitions are $a$-transitions; all rightward transitions are $b$-transitions.
One final optimization can be obtained by observing that one may identify states $(k-1, 1)$ with $(k, 0)$ without affecting the automaton's behavior: Neither is an accepting state, and both go to $(0, 0)$ on an $a$ and to $(k, 0)$ on a $b$. This saves one state and reduces the total state count from $\frac{(k+1)(k+2)}{2}$ to $\frac{k(k+3)}{2}$.
Previous, flawed approach. Have a set of states that essentially counts how many characters it's been since the last $a$. You don't need to count past $k$, so the number of states is finite. If you end up in a state where there's been fewer than $k$ characters since the last $a$, you accept; if you end up in a state where there's been at least $k$ characters since the last $a$, you reject.
(ETA: This of course fails to count how many characters there are in the string. Deepest thanks to J.-E.Pin for pointing this out in the comments.)