Consider the set of strings on $\{0,1\}$ in which, every substring of $3$ symbols has at most two zeros. For example, $001110$ and $011001$ are in the language, but $100010$ is not. All strings of length less than $3$ are also in the language. A partially completed $\text{DFA}$ that accepts this language is shown below.
The missing arcs in the $\text{DFA}$ are:
- $\begin{array}{|l|l|l|l|l|l|}\hline \textbf{} & \textbf{00} & \textbf{01} & \textbf{10}& \textbf{11} & \textbf{q} \\\hline \textbf{00} & \text{1} & \text{0} & \text{}& \text{} & \text{} \\\hline \textbf{01} & \text{} & \text{} & \text{}& \text{1} & \text{} \\\hline \textbf{10} & \text{0} & \text{} & \text{}& \text{} & \text{} \\\hline \textbf{11} & \text{} & \text{} & \text{0}& \text{} & \text{} \\\hline \end{array}$
- $\begin{array}{|l|l|l|l|l|l|}\hline \textbf{} & \textbf{00} & \textbf{01} & \textbf{10}& \textbf{11} & \textbf{q} \\\hline \textbf{00} & \text{} & \text{0} & \text{}& \text{} & \text{1} \\\hline \textbf{01} & \text{} & \text{1} & \text{}& \text{} & \text{} \\\hline \textbf{10} & \text{} & \text{} & \text{}& \text{0} & \text{} \\\hline \textbf{11} & \text{} & \text{0} & \text{}& \text{} & \text{} \\\hline \end{array}$
- $\begin{array}{|l|l|l|l|l|l|}\hline \textbf{} & \textbf{00} & \textbf{01} & \textbf{10}& \textbf{11} & \textbf{q} \\\hline \textbf{00} & \text{} & \text{1} & \text{}& \text{} & \text{0} \\\hline \textbf{01} & \text{} & \text{1} & \text{}& \text{} & \text{} \\\hline \textbf{10} & \text{} & \text{} & \text{0}& \text{} & \text{} \\\hline \textbf{11} & \text{} & \text{0} & \text{}& \text{} & \text{} \\\hline \end{array}$
- $\begin{array}{|l|l|l|l|l|l|}\hline \textbf{} & \textbf{00} & \textbf{01} & \textbf{10}& \textbf{11} & \textbf{q} \\\hline \textbf{00} & \text{} & \text{1} & \text{}& \text{} & \text{0} \\\hline \textbf{01} & \text{} & \text{} & \text{}& \text{1} & \text{} \\\hline \textbf{10} & \text{0} & \text{} & \text{}& \text{} & \text{} \\\hline \textbf{11} & \text{} & \text{} & \text{0}& \text{} & \text{} \\\hline \end{array}$
