made easy test series 2023 toc question

Question

How many states are there in a minimum state DFA accepting the language  number of 0’s is divisible by 2 and number of 1’s is divisible by 7, respectively?

Answer 1

For this, we have to calculate no of states of these two DFA separately, then we have to multiply it, and it will give minimum numbers of states for the given DFA. 

 

$(\ No. \ of \ 0's \ div \ by \ 2\ ) * ( \ No. \ of \ 1's \ div \ by \ 7 \ )$

= $(\ N₀\ mod \ 2 \ ) \ * \ (\ N₁ \ mod \ 7\ )$

= { $0, 1$ } $*$ { $0, 1, 2, 3, 4, 5, 6$ }     [ As Mod 2 gives 0, 1 as remainder and mod 7 gives 0 to 6 as remainder ]

= $2 * 7$

= $14$

No. of states will be: $14$

 

Good read : 

1.  Gate Cse 2001 - Min no of states in DFA

2.  Minimal Deterministic Finite Automata