Gate mock test

Question

please explain answer given is 5

Comments

Division by 2, ending with 0

Division by 4, ending with 00

Division by 8, ending with 000

Division by 16 ending with 0000

Hence 5 states are enough.

---

@Ashwin Kulkarni
question :- set of all string of 0's and 1's where every string contains at least 3 0's and 4 1's then states in minimal finite automata??
ARGUMENT:- then in minimal finite automata, we have 3 zeros and 4 1's total 7
 can we say that it will have 8 states in minimal FA ???

---

It is not good to say directly by any co-relation, by deriving strings and then drawing NFA  will be better way. And

3 0's and 4 1's / 3 0's or 4 1's also matters.

Answer 1

 

lets us suppose we have to make DFA of whose integer equivalent is divisible by  x

then write the x in the form of  $2^{k}*m$ where m is odd no

then the minimum no of state in the DFA  will be k+m

now we will understand  it by using examples  

ex1    divisible by 16 

then write 16 in form of  $2^{k}*m$  ( $2^{4}*1$)  so 4+1=5 answer

ex2    divisible by 12

then write 12 in form of  $2^{k}*m$  ( $2^{2}*3$)  so 2+3=5 answer

ex3    divisible by 18

then write 18 in form of  $2^{k}*m$  ( $2^{1}*9$)  so 1+9=10 answer