1

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

attempt in graph

I tried then to do it for $k=1$ and $k=2$.

enter image description here

But I don't know how to generalize...

Revolucion for Monica
  • 1,511

1 Answers1

1

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

enter image description here

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.)

Brian Tung
  • 34,160
  • Than you for your answer. I updated my question with an attempt. Yet, I think my attempt isn't really smart even though it meets the constraints... – Revolucion for Monica Mar 14 '17 at 15:37
  • @Marine1: Your attempt won't work (hint: except for $k = 1$). You need to have enough states to actually count the number of characters since the last $a$, not just say whether it's below $k$ or not. For instance, suppose $k = 2$. Then you need how many states? Then suppose $k = 3$; in that case, you need how many states? – Brian Tung Mar 14 '17 at 15:40
  • yes but I can't do a state for each of $k$ values ? example – Revolucion for Monica Mar 14 '17 at 15:48
  • @brian-tung How many states do you get for your DFA? – J.-E. Pin Mar 14 '17 at 19:08
  • @Marine1: Why not? I'm not sure I see a way to do it without something like that. – Brian Tung Mar 14 '17 at 21:36
  • @J.-E.Pin: $k+1$ (numbered most conveniently $0$ through $k$). For instance, with $k = 2$, I need a state $0$ for when I've just started, or when I've just gotten an $a$, and I need a state $1$ when I've just gotten a $b$ after previously getting an $a$ (or just starting), and I need a state $2$ for when I've just gotten (at least) two $b$s in a row. – Brian Tung Mar 14 '17 at 21:38
  • Then I am afraid your answer is plain wrong. The minimal DFA has $k(k+3)/2$ states. – J.-E. Pin Mar 14 '17 at 21:40
  • @J.-E.Pin: Maybe I'm misinterpreting the language? Otherwise, why doesn't a linear count work here? I'm interpreting the language as containing those words with at least one $a$ in the last $k$ characters. Did I miss a specification of exactly one $a$? That would make the space $O(k^2)$, I could see that. – Brian Tung Mar 14 '17 at 21:42
  • Just try by hand with the language $A^*(A^2 - bb)$, where $A = {a,b}$. The minimal DFA has 5 states. – J.-E. Pin Mar 14 '17 at 21:46
  • @J.-E.Pin: I will concede I must be missing something. Let $Q = {0, 1, 2}, \Sigma = {a, b}, \delta(0, a) = 0, \delta(0, b) = 1, \delta(1, a) = 0, \delta(1, b) = 2, \delta(2, a) = 0, \delta(2, b) = 2, q_0 = 0, F = {0, 1}$. What string in that language is not accepted, or what excluded string is accepted? – Brian Tung Mar 14 '17 at 21:53
  • Only words of length $\geq 3$ should be accepted. For instance, the empty word and $a$ should not be accepted. – J.-E. Pin Mar 14 '17 at 21:58
  • @J.-E.Pin: Ahh, of course, thanks. I'll reconstruct. – Brian Tung Mar 14 '17 at 22:02
  • Very nice answer. – J.-E. Pin Mar 16 '17 at 22:20
  • @J.-E.Pin: Thanks, I couldn't do it without your assistance. :-) – Brian Tung Mar 16 '17 at 23:06