Given alphabet $\Gamma = \{0,1\}$, let $L = \{\omega : All\ words\ ending\ 010\}$ be a language. Find an automaton. I have to find an automaton using sliding window method.. First I need some explanation of the sliding window method. If I google it, all I get is sliding window protocol something that is not related computer science I think. My professor gave me some hint.
Hint: Let $S = \{\epsilon, \underbrace{1st\ word}_{All\ words\ length\ 1}, \underbrace{2nd\ word}_{All\ words\ length\ 2},\ldots\}$ be a set. Use sliding window of length 3. Given $u_0u_1u_2 \ldots$ $$\underbrace{u_0u_1u_2}_{window\ 1}, \underbrace{u_1u_2u_3}_{window\ 2},\ldots$$
I dont know what $u_0u_1u_2 \ldots$ is but it is given. I think it is states... Any idea??
The string $u_0u_1u_2u_3\ldots$ is the stream of input characters; in this case each $u_k$ is a $0$ or a $1$. The sliding window approach is to imagine that you’re looking at this input through a window that lets you see $3$ characters at a time — $3$ because that’s the length of the pattern string, $010$, that you’re looking for. First you see just $u_0u_1u_2$; then you see just $u_1u_2u_3$; then $u_2u_3u_4$; and so on. You want to design the automaton so that its state is determined by the current window contents. That is, if it’s read $u_0u_1u_2u_3u_4u_5u_6$, its state should be determined by what’s in the window at that point, namely, $u_4u_5u_6$. If that’s $010$, it should be in an acceptor state; if that’s not $010$, it should not.
Suppose, for instance, that the input stream starts out $101010010101$; the automaton should be in an acceptor state at each of the windows shown in brown below:
$$\begin{align*} &1\color{brown}{010}10010101\\ &101\color{brown}{010}010101\\ &101010\color{brown}{010}101\\ &10101001\color{brown}{010}1 \end{align*}$$
Had the input stopped at any of those four points, the string would have been in $L$ and would have been accepted.
Let $q_0$ be the initial state. You want the automaton to idle there until it it gets the first character of the search pattern; the pattern is $010$, so the first automaton should idle at $q_0$ until it receives a $0$ input. On a $0$ input it should go to a new state, $q_1$, representing the fact that it’s one character into a possible instance of the pattern. Thus, the transitions for $q_0$ should be $$q_0\overset{0}\longrightarrow q_1\qquad q_0\overset{1}\longrightarrow q_0\;.$$
In state $q_1$ it’s looking for the second character of the pattern, $1$. If instead it gets a $0$, it should stay in state $q_1$: if that $0$ is part of the pattern at all, it must be the first character, and the $0$ that got us to $q_1$ in the first place isn’t part of an instance of the pattern after all. Thus, being in state $q_1$ means that we’re one character into a possible instance of $010$. An input of $1$ then puts us two characters into a possible instance; this is something new and needs a new state, $q_2$, to represent it.
I’ll stop here and leave the rest of the design to you; feel free to leave a comment if you get stuck. I frankly don’t understand why it was suggested that you look at $S$, unless the idea was to get you thinking in terms of looking at longer and longer substrings of the input.