Consider a DFA over Σ = {a, b} that accepts all strings in which the number of…
2001
Consider a DFA over Σ = {a, b} that accepts all strings in which the number of a's is divisible by 6 and the number of b's is divisible by 8. What is the minimum number of states required?
- A.
8
- B.
14
- C.
15
- D.
48
Attempted by 36 students.
Show answer & explanation
Correct answer: D
The DFA must remember two independent pieces of information: the remainder of the number of a's modulo 6 and the remainder of the number of b's modulo 8.
There are 6 possible remainders for count(a) mod 6: 0, 1, 2, 3, 4, 5.
There are 8 possible remainders for count(b) mod 8: 0, 1, 2, 3, 4, 5, 6, 7.
A state can therefore be represented as a pair (i, j), where i = count(a) mod 6 and j = count(b) mod 8.
Number of possible pairs = 6 × 8 = 48.
The accepting state is (0, 0), because both counts must be divisible by their respective numbers. Different remainder pairs may need different suffixes to reach (0, 0), so they cannot be merged in the minimum DFA.
Therefore, the minimum number of states is 48. Hence, option D is correct.