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 DFA that accepts this language is shown below. The missing arcs in the DFA are

The condition requires that no substring of length $3$ contains three zeros (i.e., the substring $000$ is forbidden). Any string containing $000$ transitions to the dead/trap state $q$.

In the DFA, each state tracks the 2-symbol suffix of the string processed so far:

• From state $00$:

  • On receiving input 0: The 3-symbol suffix is 000 (forbidden), so it must transition to trap state $q$.

  • On receiving input 1: The suffix becomes 01, so it transitions to state $01$.

• From state $01$:

  • On receiving input 0: Suffix becomes 10 (transition already present in the DFA).

  • On receiving input 1: Suffix becomes 11, so it must transition to state $11$.

• From state $10$:

  • On receiving input 0: Suffix becomes 00, so it must transition to state $00$.

  • On receiving input 1: Suffix becomes 01 (transition already present in the DFA).

• From state $11$:

  • On receiving input 0: Suffix becomes 10, so it must transition to state $10$.

  • On receiving input 1: Suffix remains 11 (self-loop transition already present in the DFA).

Summarizing the missing transitions:

• From $00$: input 1 goes to $01$, input 0 goes to $q$

• From $01$: input 1 goes to $11$

• From $10$: input 0 goes to $00$

• From $11$: input 0 goes to $10$

This transition table matches (D).