207 views

retagged | 207 views
0
5 state for MDFA??
0
can you explain a bit further ...?
0
try for div by 2,4,8... you will get generalized from.
+3
$(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
+5
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.
0
@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 ???
+1
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.

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

by Loyal (9.9k points)

1