= Solution
Use a <Moore machine> whose state records the longest suffix of the received stream that is also a prefix of the target word. The transitions are
$$
\begin{array}{c|cc|c}
\text{state}&x=0&x=1&\text{output}\\\hline
S_0&S_0&S_1&0\\
S_1&S_0&S_2&0\\
S_2&S_3&S_2&0\\
S_3&S_0&S_4&0\\
S_4&S_0&S_2&1
\end{array}.
$$
The last row preserves overlap: after recognition, one more one leaves suffix $11$, giving $S_2$. Initialize to $S_0$ and update the state on each active clock edge; the output after that edge reports whether the word has just ended. This is a <prefix-suffix sequence recognizer>.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/digital-systems-sequence-recognizer.png]
{title=State transitions of the overlapping <Moore machine> recognizer}
{description=Edge labels are input bits. Only the shaded, double-ring state produces output one.}
Back to article page
