0

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

eChung00
  • 2,963
  • 8
  • 29
  • 42

1 Answers1

2

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.

Brian M. Scott
  • 616,228
  • Thank you for the answer...I just looked at it and it seems very helpful... I think I have to read it again and try to complete the design.. I will add comment if I have more question... – eChung00 Oct 27 '13 at 23:33
  • So the automaton has to have four states, lets say $q_0q_1q_2q_3.$ The transitions go $q_0 \rightarrow q_1 \rightarrow q_2 \rightarrow q_3,$ where $q_0$ is initial state, $q_3$ is final state. And there would be loop with input 1 at $q_0$, with input 0 at $q_1$, with 1 at $q_2$, and final state is $q_3$. Is this correct?? – eChung00 Oct 27 '13 at 23:40
  • What about the $\epsilon$ input?? How do I take care of it?? – eChung00 Oct 27 '13 at 23:45
  • @eChung00: Not quite right: you can’t loop at $q_2$ with $1$, because then you would accept $0110$, for instance. If you’re in $q_2$ and get a $1$, you have to start over: it’s as if you had received no input at all. You also have to specify transitions from the accepting state $q_4$. If you get a $0$, you need to go back to $q_1$, the state that indicates that you’re one-third of the way to getting $010$; where should you go if you get a $1$, meaning that your current window shows $101$? Empty input is no problem: it leaves you at $q_0$, which is not an acceptor state. – Brian M. Scott Oct 28 '13 at 11:58