The Gateway to Computer Science Excellence
+24 votes
2.8k views
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 $\}.$
in Theory of Computation by
retagged by | 2.8k views
+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 ....

Correct 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.

Ref:- https://stackoverflow.com/questions/21897554/design-dfa-accepting-binary-strings-divisible-by-a-number-n#

0

   +1 for the links!

2 Answers

+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 $

by
edited by
+1
Then for designing a DFA divisible by n, we require minimum of n states?
+8
Not in case of even n.
+1
why not in case of even n??
+6
some of them get minimized
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).
0
then what is the given DFA doing? Or did you interpret the leading zeroes as going to a dead state?
0
No, sir  

I mean leading zero will loop in the first state...i,e 0th state.

Do i interpret it wrong?
0
that's the given DFA rt?
0
sir can u tell me.How I can attach a image here?

I am unable to that.
0

I....

+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
missed these two transitions:

state 4 on 0 goes to state 3

state 5 on 1 goes to state 1
0
Then state 5 and state 0 both will become equivalent. And I hope both states 5,0 are finals too
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????
0
actually 0 is also divisible by 5 (or by any num). so state 0 should be final too
+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.
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:

https://stackoverflow.com/a/33575441/631823

https://stackoverflow.com/questions/21897554/design-dfa-accepting-binary-strings-divisible-by-a-number-n#

+7 votes

Ans...

here q0 is the initial state and final state

by
0

 will help in better understanding above described method...........

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
52,345 questions
60,484 answers
201,812 comments
95,289 users