GATE 2025 CS1 Q.50: solution and answer

GATE 2025 · CS1Q.50 · 2 marks · MSQ

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

GATE 2025 CS1 question 50: A DFA with four states in a row, left to right: q_0 (start, arrow entering from the left), q_1, q_2, q_3 (q_3 is… — Figure from the GATE 2025 CS1 paper. It is part of the question.

(A)
The set of all strings containing an even number of $b$ 's.
(B)
The set of all strings containing the pattern $bab$ .
(C)
The set of all strings ending with the pattern $bab$ .
(D)
The set of all strings not containing the pattern $aba$ .

Answer and solution

ANSWER

Only (C) is correct: the DFA accepts exactly the strings ending with $bab$ .

Official answer: CSource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

Read the DFA from the figure. States $q_{0}$ (start), $q_{1}$ , $q_{2}$ , $q_{3}$ ; $q_{3}$ is the only accepting state. Transitions: $δ (q_{0}, a) = q_{0}$ , $δ (q_{0}, b) = q_{1}$ , $δ (q_{1}, a) = q_{2}$ , $δ (q_{1}, b) = q_{1}$ , $δ (q_{2}, a) = q_{0}$ , $δ (q_{2}, b) = q_{3}$ , $δ (q_{3}, a) = q_{2}$ , $δ (q_{3}, b) = q_{1}$ .
Give each state a meaning: the longest suffix of the input read so far that is a prefix of $bab$ . So $q_{0}$ means no useful suffix ( $ε$ ), $q_{1}$ means $b$ , $q_{2}$ means $ba$ , and $q_{3}$ means $bab$ .
Check every transition against this meaning. From $q_{0}$ : reading $a$ gives suffix $ε$ , so $q_{0}$ ; reading $b$ gives $b$ , so $q_{1}$ . From $q_{1}$ ( $b$ ): reading $a$ gives $ba$ , so $q_{2}$ ; reading $b$ gives $bb$ , longest useful suffix $b$ , so $q_{1}$ . From $q_{2}$ ( $ba$ ): reading $a$ gives $baa$ , no useful suffix, so $q_{0}$ ; reading $b$ gives $bab$ , so $q_{3}$ . From $q_{3}$ ( $bab$ ): reading $a$ gives $baba$ , longest useful suffix $ba$ , so $q_{2}$ ; reading $b$ gives $babb$ , longest useful suffix $b$ , so $q_{1}$ . All eight transitions match, so the DFA is in $q_{3}$ exactly when the input ends with $bab$ . The language is $(a + b)^{*} bab$ , and (C) is correct.
(A) is false. The string $bbab$ ends with $bab$ , so it is accepted ( $q_{0} \to q_{1} \to q_{1} \to q_{2} \to q_{3}$ ), but it has three $b$ 's, an odd number. Also $bb$ has an even number of $b$ 's but ends in $q_{1}$ and is rejected.
(B) is false. The string $baba$ contains $bab$ , but $q_{0} \to q_{1} \to q_{2} \to q_{3} \to q_{2}$ ends in the non-accepting state $q_{2}$ , so it is rejected.
(D) is false. The string $a$ does not contain $aba$ , but it ends in $q_{0}$ and is rejected. Also $abab$ contains $aba$ yet is accepted ( $q_{0} \to q_{0} \to q_{1} \to q_{2} \to q_{3}$ ).

KEY IDEA

Label each state with the longest suffix of the input that is a prefix of the pattern $bab$ , and check every transition. The DFA is then the standard pattern-matching automaton for strings ending in $bab$ .

WATCH OUT FOR

Choosing (B) because the automaton is a $bab$ -detector. Here the accepting state $q_{3}$ has outgoing transitions to $q_{2}$ and $q_{1}$ , so it is not absorbing and the DFA remembers only the last few symbols. Accepting means the input ENDS with $bab$ , not that it contains $bab$ .

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 18 Finite automata questions, with notes

GATE 2025 CS1 Q.50: solution and answer

Answer and solution

More Finite automata questions