The minimum possible number of states of a deterministic finite automaton that accepts the regular language L = {w1 a w2 | w1, w2 ∈ {a,b}*, |w1| = 2, |w2| ≥ 3} is ____.
Explanation
Track position: 3 states to count the first 2 characters and reach the mandatory 'a' at position 3 (s0, s1, s2). If the 3rd character isn't 'a', go to a permanent trap/reject state (1 state) — the string can never be in L regardless of what follows, since w1's length is fixed at exactly 2. If it IS 'a', track how many characters have followed so far, saturating at 3 (t0, t1, t2, t≥3-accepting) — 4 states. Total = 3 + 1 + 4 = 8 states, and this is minimal since each state is reachable and distinguishable.
Source: GATE CS 2017 (Session 2) (2017)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.