closed by
926 views
5 votes
5 votes
closed

let the ∑ = {0,1} ===> strings possible are should be Binary strings.

No.of States in Minimal DFA that accepts, Decimal( Binary String ) = 0 mod n

 

in ACE coaching institute, i learned that

For Decimal( Binary String ) = 0 mod n

  i)   if n = 2$^m$ then No.of states in Minimal DFA = m + 1

 ii)   if  n = odd, then No.of states in Minimal DFA = n

iii)   if n = even but not power of 2, then follow division technique until your value matched with case i or  case ii

 

For example,

if n=21 ===> then No.of states in Minimal DFA = 21

if n=32 ===> then No.of states in Minimal DFA = 6

if n=22 ===> then No.of states in Minimal DFA = 12 due to ( $\frac{22}{2}$ → one time division → 11 → is odd ) ===> 1+ 11

if n=12 ===> then No.of states in Minimal DFA = 5 due to ( $\frac{12}{2}$ → $\frac{6}{2}$ → two time division → 3  →  is odd ) 2 + 3

 

But i didn’t know how it is prove it, i mean what is the logic behind that ?

 

what is the answer for following questions ?

Decimal( Binary String ) = 0 mod x  or  0 mod y  

  1. neither x divides y nor y divides x
  2. either x is divides y or y divides x
closed by

Related questions

1 votes
1 votes
1 answer
2
prasitamukherjee asked Jun 23, 2015
397 views
I can't really understand the difference between the two statements :a)for all x(C(x)->F(x))b)there exists x(C(x)->F(x))C(x)=x is a comedianF(x)=x is funnythe domain cons...
2 votes
2 votes
1 answer
3
Pranavpurkar asked Nov 11, 2022
389 views
Consider the following language over $\sum$ = {0, 1}L = {w | w $\epsilon \sum$ * and |w| is divisible by 2 and not by 4}How many sates will min-DFA accepting L will have?...