The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes

please explain answer given is 5

asked in Theory of Computation by Junior (515 points)
retagged by | 204 views
5 state for MDFA??
can you explain a bit further ...?
try for div by 2,4,8... you will get generalized from.
$(0+1)^*0000$ // all strings of this form are divisible by 16.Last 4 digits are giving remainder.And for divisibility remainder should be 0.

5 states
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.

1 Answer

0 votes


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


answered by Loyal (9.5k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,412 questions
53,594 answers
70,878 users