How many states are there in a minimum state deterministic finite automation…
2014
How many states are there in a minimum state deterministic finite automation accepting the language L = {w | w {0,1} number of 0's is divisible by 2 and number of 1's is divisible by 5, respectively} ?
- A.
7
- B.
9
- C.
10
- D.
11
Attempted by 120 students.
Show answer & explanation
Correct answer: C
To construct a minimum state DFA for this language, we need to track the remainder of the count of 0's modulo 2 and the count of 1's modulo 5. This requires 2 states for the 0-count condition and 5 states for the 1-count condition. Since these conditions are independent, the total number of states in the minimal DFA is the product of the individual moduli: 2 × 5 = 10 states.