The GATE Grind

GATE 2025 CS (CS1) – Question 50

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Multiple select

Consider the following deterministic finite automaton (DFA) defined over the alphabet, $\Sigma = \{a,b\}$. Identify which of the following language(s) is/are accepted by the given DFA.

states q0 (start), q1, q2, q3 (accepting). Transitions: q0 -a-> q0, q0 -b-> q1; q1 -b-> q1, q1 -a-> q2; q2 -b-> q3, q2 -a-> q0; q3 -a-> q2, q3 -b-> q1.
  1. The set of all strings containing an even number of $b$'s.
  2. The set of all strings containing the pattern $bab$.
  3. The set of all strings ending with the pattern $bab$.
  4. The set of all strings not containing the pattern $aba$.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) The set of all strings ending with the pattern $bab$.

Explanation

The states track the longest suffix matching a prefix of 'bab': q0 = none, q1 = b, q2 = ba, q3 = bab. The accepting state q3 has outgoing transitions (a→q2, b→q1), so it is not absorbing. The DFA accepts exactly the strings ending in bab.