Consider the regular language L = (111 + 11111)*. The minimum number of states…

Answer: 9

Explanation:

• The language consists of strings of 1s whose lengths are sums of 3s and 5s (lengths representable as 3a + 5b with a,b ≥ 0).

• List small representable lengths: 0 (empty), 3, 5, 6, 8, 9, 10, ... . The lengths 1, 2, 4 and 7 are not representable.

• By the Frobenius coin problem for 3 and 5, the largest nonrepresentable length is 7, so every length ≥ 8 is representable and thus accepted.

• Apply Myhill–Nerode: two lengths m and n are distinguishable if there exists some k such that m+k is accepted but n+k is not (or vice versa). The continuation behaviours for lengths 0,1,2,3,4,5,6,7 are pairwise different, while all lengths ≥ 8 have the same behaviour (always accepted).

• Therefore the minimal DFA requires one state for each length 0–7 (8 states) plus one accepting sink state for all lengths ≥ 8, totaling 9 states.

Conclusion: the minimum number of states in any DFA accepting (111 + 11111)* is 9.