A minimum state deterministic finite automation accepting the language L = {W |W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has
A)15 States
B)11 states
C)10 states
D)9 states

Question

Quizplus · Accepted Answer

To construct a minimum state deterministic finite automaton (DFA) for the given language, we need to consider the divisibility by both 3 and 5. For divisibility by 3, we need 3 states (to count the number of 0's modulo 3), and for divisibility by 5, we need 5 states (to count the number of 1's modulo 5). Since we need to track both conditions simultaneously, we multiply the number of states needed for each condition, resulting in 3 * 5 = 15 states.

A Minimum State Deterministic Finite Automation Accepting the Language L