GATE CS 2009 Q41 — Regular Expressions and Finite Automata

Let the states of the given DFA be $q_0$ (start state), $q_1$, and $q_2$ (accepting state). The transitions are as follows:

• From $q_0$: on input $1$ it loops to $q_0$, and on $0$ it transitions to $q_1$.
• From $q_1$: on input $1$ it goes back to $q_0$, and on $0$ it transitions to the accepting state $q_2$.
• From $q_2$: on input $0$ it loops to $q_2$, and on $1$ it goes back to $q_0$.

Let us analyze the behavior of this DFA:

• State $q_0$: Represents the state where the string processed so far does not end with $0$.
• State $q_1$: Represents the state where the string processed so far ends with a single $0$ (i.e., suffix is $0$ but not $00$).
• State $q_2$ (Accepting): Represents the state where the string processed so far ends with at least two $0$s (i.e., suffix is $00$).

Whenever a $1$ is encountered, the suffix condition is broken, and the DFA resets to $q_0$. Thus, the DFA reaches the accepting state $q_2$ if and only if the string ends with $00$.

Eliminating other options:

• Option A: The string $0$ begins with $0$ but is not accepted (ends in $q_1$).
• Option B: The string $0$ ends with $0$ but is not accepted.
• Option D: The string $001$ contains the substring $00$, but processing it leads to $q_0$ (non-accepting), so it is rejected.

Therefore, the DFA accepts the set of all strings that end with $00$.