Consider a DFA over Σ = {a, b} accepting all strings which have number of a’s…
2001
Consider a DFA over Σ = {a, b} accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. What is the minimum number of states that the DFA will have?
- A.
8
- B.
14
- C.
15
- D.
48
Attempted by 58 students.
Show answer & explanation
Correct answer: D
To accept strings where the number of a's is divisible by 6, a DFA needs at least 6 states to track remainders modulo 6. Similarly, tracking b's divisible by 8 requires at least 8 states for modulo 8 remainders. Since these conditions are independent, the minimum DFA uses the product of states, resulting in 6 multiplied by 8 equals 48 states.
A video solution is available for this question — log in and enroll to watch it.