Consider the following deterministic finite automaton (DFA) defined over the alphabet Sigma = {a, b}. The DFA has 4 states q0 (start), q1, q2, q3 (accept). Transitions: q0 --a--> q1, q0 --b--> q0; q1 --a--> q1, q1 --b--> q2; q2 --a--> q1, q2 --b--> q3; q3 --a--> q3, q3 --b--> q3 (q3 is a dead/trap state for some interpretations). Looking at the DFA image: start state with self-loop on b, transitions on a lead forward, and the accept state is reached after seeing pattern 'abb'. Identify which of the following language(s) is/are accepted by the given DFA. A. The set of all strings containing an even number of b's. B. The set of all strings containing the pattern abb. C. The set of all strings not starting with a. D. The set of all strings containing the pattern aba.

GATE 2025 · Theory of Computation · Finite Automata · easy

Answer: Option B: The set of all strings containing the pattern abb.

1. Trace the DFA on test strings: String 'abb': q0 -a-> q1 -b-> q2 -b-> q3 (ACCEPT). String 'babb': q0 -b-> q0 -a-> q1 -b-> q2 -b-> q3 (ACCEPT). String 'ab': q0 -a-> q1 -b-> q2 (REJECT, not in accept state). String 'bba': q0 -b-> q0 -b-> q0 -a-> q1 (REJECT).
2. Match to the given options: Option A (even number of b's): 'abb' has 2 b's (even) and is accepted, but 'aabb' has 2 b's and is also accepted. However, 'abba' is accepted (has 2 b's) — seems consistent. BUT 'abbb' (3 b's, odd) is also accepted since it contains 'abb'. So A is NOT the language. Option B (contains pattern abb): Every string accepted must have passed through q1->q2->q3, meaning it contains 'abb'. And any string containing 'abb' will eventually reach q3. So B matches. Options C and D: The DFA accepts strings starting with a (like 'abb'), so C is wrong. 'aba' does not lead to q3 (q0-a->q1-b->q2-a->q1, stuck at q1), so D is wrong.