A minimum state deterministic finite automaton accepting the language L={w | w…

Answer: 15 states

Reasoning:

• States represent pairs of remainders (r0, r1), where r0 is the number of 0s modulo 3 (values 0,1,2) and r1 is the number of 1s modulo 5 (values 0,1,2,3,4).

• Total number of distinct states needed is 3 × 5 = 15.

• Start state is (0,0). A state is accepting exactly when both components are 0, i.e., (0,0).

• Transitions: reading symbol 0 updates the first component (r0) by +1 mod 3 and leaves r1 unchanged; reading symbol 1 updates the second component (r1) by +1 mod 5 and leaves r0 unchanged.

• Minimality sketch: any two different pairs (a,b) and (c,d) are distinguishable. Choose a suffix that makes one pair reach (0,0) while the other does not (for example, appropriate numbers of 0s and/or 1s to correct one pair's remainders to zero modulo their moduli but not the other's). Thus no two of the 15 states are equivalent, so all 15 are necessary.