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 language is $\{a,b\}$.

Reformulation : the question is like : 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$ ?


Browse other questions tagged or ask your own question.