I hav forgot from where i read it ...

**The minimum DFA that accept all base "M" system which are divisible by "N" contains N state ....**

**Co**rrect me if i am wrong .....

The Gateway to Computer Science Excellence

+24 votes

Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:

$L=\{w \in \{0, 1\}^* \mid w$ interpreted as binary number (ignoring the leading zeros) is divisible by five $\}.$

$L=\{w \in \{0, 1\}^* \mid w$ interpreted as binary number (ignoring the leading zeros) is divisible by five $\}.$

+1

I hav forgot from where i read it ...

**The minimum DFA that accept all base "M" system which are divisible by "N" contains N state ....**

**Co**rrect me if i am wrong .....

0

yes.|E|=k mod n or |E| mod n=k where n will be the no of states and k decides which no of state among n is final state.

+1

Language that accepts **binary strings whose decimal equivalent is divisible by n.**

minimal dfa for this language does not always have n states..

https://gateoverflow.in/263964/gatebook-2019-toc1-7

For binary strings--

$\bullet$ if n is odd then we need n states in mDFA.

$\bullet$ if n is a power of 2 (let's say $2^k$ ) then we need k+1 states.

+42 votes

Best answer

Suppose we have decimal no $3$ after that we get a symbol $2$ . it becomes $32$ as $3 x 10 +2 = 32 $

In binary if we have $10$ ( i.e $2$ in decimal say old no) and after that we get symbol $1$ it become $101$( i.e $5$ in decimal say new no )

$ 2$ (old no.) $ \times 2$( base) $+1$( input symbol) $= 5$ (new no.)

Now in the given problem, binary no is divisible by $5$ , i.e $0,101,1010,1111..... $

We need $5$ states in DFA , $0,1,2,3$ and $4$ .Each state represent remainder that comes when we divide no by $5$.

Input symbol $=\{0,1\}$

We get the transition:

[Old state $\times$ base $+$ input symbol] mod $5 =$ New state , where base is $2$

$[0 \times 2 + 0]mod \ 5 = 0$ $[1 \times 2 + 0]mod \ 5 = 2$ $[2 \times 2 + 0]mod \ 5 = 4$

$[0 \times 2 + 1]mod \ 5 = 1$ $[1 \times 2 + 1]mod \ 5 = 3$ $[2 \times 2 + 1]mod \ 5 = 0$

$[3 \times 2 + 0]mod \ 5 = 1$ $[4 \times 2 + 0]mod \ 5 = 3$

$[3 \times 2 + 1]mod \ 5 = 2$ $[4 \times 2 + 1]mod \ 5 = 4 $

0

@Arjun sir

Ignoring the leading zeros is given in question, So shouldn't it be 6 state from state 0(not final state),1,2,3,4,5(final state).

Ignoring the leading zeros is given in question, So shouldn't it be 6 state from state 0(not final state),1,2,3,4,5(final state).

0

0

+1

@ ana , any binary number starting with more than 4 1's will not be accepted by above DFA, say 1111101, i,e 125

0

no only state 5 is the final state.

ignoring the leading zeros, is given in the question....so state 0 is not the final state.

That's what I was saying so long....

M i wrong????

ignoring the leading zeros, is given in the question....so state 0 is not the final state.

That's what I was saying so long....

M i wrong????

+2

yes, for designing a DFA divisible by n, then total n states required. each state represent remainder ( 0 to n-1 remainder ) that comes when we divide no by n.

0

Since initial state is the final state here, so this will accept ⋵ (epsilon) too.. but ⋵

is not a part of the language L.

is not a part of the language L.

0

Minimal DFA that accept all Binary number's divisible by $5=5\ states$

$0$ | $1$ | |

$q0$ | $q0$ |
$q1$ |

$q1$ | $q2$ |
$q3$ |

$q2$ | $q4$ |
$q0$ |

$q3$ | $q1$ | $q2$ |

$q4$ | $q3$ | $q4$ |

+1

DFAs drawn with this technique will be minimized DFA only when there is no common factor between number **n** and base** b**, e.g. between 5 and 2, or between 5 and 3.

Like for example in binary numbers,* if the divisor is a power of 2 (i.e. 2^n) then the minimum number of states required will be n+1.* How would you design such an automaton? Just see the properties of binary numbers. For a number, say 8 (which is 2^3), all its multiples will have the last 3 bits as 0. For example, 40 in binary is 101000. Therefore for a language to accept any number divisible by 8 we just need an automaton which sees if the last 3 bits are 0, which we can do in just 4 states instead of 8 states. That's half the complexity of the machine.

In fact, this can be extended to any base. For a ternary base number system, if for example we need to design an automaton for divisibility with 9, we just need to see if the last 2 numbers of the input are 0. Which can again be done in just 3 states.

So for any odd number n in a binary system, we need n states to define the language which accepts all multiples of n. On the other hand, if the number is even but not a power of 2 (only in case of binary numbers) then we need to divide the number by 2 till we get an odd number and then we can find the minimum number of states by adding the odd number produced and the number of times we divided by 2.

*For example, if we need to find the minimum number of states of a DFA which accepts all binary numbers divisible by 20, we do :*

*20**/**2* *=* *10*
*10**/**2* *=* *5*

*Hence our answer is **5 + 1 + 1 = 7**. (The 1 + 1 because we divided the number 20 twice).*

**Source**:

52,345 questions

60,484 answers

201,812 comments

95,289 users