GATE CS 2025 Set 1 | Question 50

MSQ · 2 marks

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.

DFA with four states in a row over a and b; the leftmost is the start state and the rightmost is the only accepting state
  1. Option A: The set of all strings containing an even number of \(b\)’s.
  2. Option B: The set of all strings containing the pattern \(bab\).
  3. Option C: The set of all strings ending with the pattern \(bab\). (correct)
  4. Option D: The set of all strings not containing the pattern \(aba\).

Answer

(C)

Explanation

Label the states \(q_0\) (start), \(q_1\), \(q_2\), \(q_3\) (accepting) from left to right. \(q_0\) loops on \(a\) and goes to \(q_1\) on \(b\); \(q_1\) loops on \(b\) and goes to \(q_2\) on \(a\); \(q_2\) goes to \(q_3\) on \(b\) and back to \(q_0\) on \(a\); \(q_3\) goes to \(q_2\) on \(a\) and to \(q_1\) on \(b\).

So \(q_1\), \(q_2\) and \(q_3\) mean that the input read so far ends with \(b\), \(ba\) and \(bab\). The DFA accepts exactly the strings ending with \(bab\), so (C) is correct.

  • (A) is wrong: \(bb\) has an even number of \(b\)'s but is rejected, while \(babab\) has three and is accepted.
  • (B) is wrong: \(baba\) contains \(bab\) but ends in \(q_2\).
  • (D) is wrong: \(b\) does not contain \(aba\) but is rejected.

Answer: C