GATE CS 2021 Set 1 Q38 — Regular Expressions and Finite Automata

To construct a Deterministic Finite Automaton (DFA) that accepts the language $L = \{ w \in \{0,1\}^* \mid w \text{ ends with } 011 \}$, we define states based on the longest suffix of the input processed so far that is also a prefix of $011$:

• $q_0$ (Initial state): Suffix is $\epsilon$ (no progress towards $011$).
• $q_1$: Suffix is $0$.
• $q_2$: Suffix is $01$.
• $q_3$ (Final state): Suffix is $011$.

Let us determine the transitions for each state:

• From $q_0$: On $0$, go to $q_1$ (progresses to $0$). On $1$, stay at $q_0$.
• From $q_1$: On $0$, stay at $q_1$ (the suffix is still $0$). On $1$, go to $q_2$ (progresses to $01$).
• From $q_2$: On $0$, go to $q_1$ (the suffix becomes $010$, whose longest matching prefix is $0$). On $1$, go to $q_3$ (progresses to $011$).
• From $q_3$: On $0$, go to $q_1$ (the suffix becomes $0110$, whose longest matching prefix is $0$). On $1$, go to $q_0$ (the suffix becomes $0111$, which has no prefix match).

This exact transition behavior is correctly represented by the DFA in Option D.