Consider the set of strings on (formula) in which, every substring of 3… — GATE CS 2012 Q46

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:

Choose one optionA

\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}

View worked solution

Answer: D

In this DFA, each non-trap state represents the last two symbols read from the input string. The state $q$ acts as the dead (trap) state, which is reached if three consecutive zeros ( $000$ ) are detected.

We can determine the missing transitions by tracking the last two symbols after reading a new input symbol:

From state $00$ :
- Reading $0$ results in $000$ (invalid), so it must transition to the trap state $q$ . Thus, $00 \xrightarrow{0} q$ .
- Reading $1$ results in the last two symbols being $01$ , so it transitions to state $01$ . Thus, $00 \xrightarrow{1} 01$ .
From state $01$ :
- Reading $1$ results in the last two symbols being $11$ , so it transitions to state $11$ . Thus, $01 \xrightarrow{1} 11$ .
From state $10$ :
- Reading $0$ results in the last two symbols being $00$ , so it transitions to state $00$ . Thus, $10 \xrightarrow{0} 00$ .
From state $11$ :
- Reading $0$ results in the last two symbols being $10$ , so it transitions to state $10$ . Thus, $11 \xrightarrow{0} 10$ .

Matching these transitions with the given tables where rows represent the source states, columns represent the destination states, and cell values represent the input symbols, we find that Option D is the correct transition table.

Free practice · Your answers on this page are not saved.

GATE CS 2012 Q46 — Regular Expressions and Finite Automata

Related questions