1
$\begingroup$

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$ ?

Improve this question
$\endgroup$
3
  • $\begingroup$ Hint: Use states to remember how long it's been since the last a you saw. $\endgroup$
    – xavierm02
    Commented Mar 13, 2017 at 22:42
  • $\begingroup$ (Or for a way bigger but "more general" solution: Use states to remember the (at most) $k$ last letters read) $\endgroup$
    – xavierm02
    Commented Mar 13, 2017 at 22:43
  • $\begingroup$ This is already covered by cs.stackexchange.com/q/1331/755 (e.g., cs.stackexchange.com/a/11051/755); see also cs.stackexchange.com/q/14008/755 and cs.stackexchange.com/q/39960/755. I suggest you read that material and try to solve your question again. If you're still stuck, edit the question to show what you've tried (after absorbing that material) and where you got stuck. $\endgroup$
    – D.W. ♦
    Commented Mar 13, 2017 at 23:48

0

Reset to default

Browse other questions tagged or ask your own question.