GATE CS 2025 Set 1 Q40 — Regular Expressions and Finite Automata

The given DFA accepts the set of all strings over $\Sigma = \{a, b\}$ that end with the pattern $bab$. We can verify this by analyzing the states and their corresponding tracking behavior:

• State $q_0$ (Start State): Represents the state where the string processed so far does not end with any prefix of $bab$ (i.e., it ends with $a$ or is empty).
• State $q_1$: Represents that the string processed so far ends with the prefix $b$.
• State $q_2$: Represents that the string processed so far ends with the prefix $ba$.
• State $q_3$ (Accepting State): Represents that the string processed so far ends with the pattern $bab$.

Let us trace the transitions from the accepting state $q_3$ to see how it maintains this property:

• If we receive an $a$ at $q_3$ (string ends in $baba$), the suffix matching the pattern becomes $ba$, so we transition to $q_2$.
• If we receive a $b$ at $q_3$ (string ends in $babb$), the suffix matching the pattern becomes $b$, so we transition to $q_1$.

Since $q_3$ is the only final state, the DFA accepts a string if and only if it ends with the pattern $bab$.