MadeEasy WorkBook: Theory of Computation - Minimum State Automata

Question

IF a number is divisible by say any integer X then what will be the minimum states required in DFA?

Comments

Answer should be x+1

---

@ Rohit Gupta 8 Could you please elaborate why 1 state extra you are considering?
If X is an integer the system could be in X state whic are 0 remainder,1 ,......X-1 remainder thus we need X states only .
Ref http://www.idt.mdh.se/kurser/cd5560/02_03/senaste_nytt/ralfs_divby3.pdf

---

I think I misinterpreted question. The question should be

IF a number is divisible by say any integer X then what will be the minimum states required in DFA accepting the number?

I interpreted it as: number is function of length of input string which is divisible by x.

Answer 1

If any no. is divisible by X then no. of states in min. DFA = 2*X

e.g. If a's divisible by 2 and input (a,b) then no. of states in min. DFA =2*2=4

If 2 no. is given like a's divisible by M and b's is divisible by N no. of states in min. DFA=M*N

e.g. If a's divisible by 3 , b's is divisible by 2  and input (a,b) then no. of states in min. DFA =2*3=6