DFA to accept a binary number divisible by 2

Question

Sorry for the bad quality picture. Which of these is correct? (1 or 2)

Answer 1

Ist one is correct 

binary no ,i.e, symbols are {0,1}   [base =2]

divisible by 2  i.e states are 0,1   representing remainder on dividing 2.

[base x state + input symbol ] mod 2  $\rightarrow$ state  

for example state is 1 and input symbol is 0 , that is(10) represent  [1 x 2 + 0 ]  = 2 and on dividing by 2 it gives remainder 0 

so[1 x 2 + 0 ] mod 2 = 0

similarly for state 0 transitions are 

[ 0 x2 + 0] mod 2 $\rightarrow$ 0

[ 0 x2 + 1] mod 2 $\rightarrow$ 1

for state 1 

[ 1 x2 + 0] mod 2 $\rightarrow$ 0

[ 1 x2 + 1] mod 2 $\rightarrow$ 1

resulting in following DFA

Answer 2

Divisible by n , so there should be n states starting from 0 to (n-1).

let's take m % n = 0 , where m is the input number .

so , the final state should be 0 .( as remainder in 0 )

For the number being divisible by 0 , the numbers can be { 0 , 10 , 100 , 110 , 1000 , 1010 .... }

So , the minimal DFA will be :

Similarly in the same manner DFA for binary number divisible by 3 will be :

Now , let's see another type of question where remainder is not zero , like find all binary numbers which when divided by 2 produces remainder 1.

So , here the number of states will be 2 , Remainder is 1 , so final state will be 1.

So , in the same way you can draw DFA for any divisiblity problem

Comments

ok :) You are correct. We just have to find the transitions for the n states. I thought you were suggesting some pattern for the transitions, which would have been handy.

---

Thank u sir :)

---

minimal DFA for divisibility check by 'n' will contain how many states ??As divisible by 4 will contain 3 states..

Answer 3

I think both of your DFA are correct, a binary number divisible by 2 must not end with 1 i.e (1110,10100.. etc all divisible by 2), and both of your dfa are working correctly for it.

Comments

Nope even Consider The Null case too . so fig a is correct !

---

Epsilon represents the empty string. So how can you convert an empty string into a binary number and divide that by 2.

The questions like number of 1's or number of 0's mod 2 = 0 will accept epsilon since 0 mod 2 = 0.

I think it should be specified in the question that the language does not contain epsilon

Answer 4

Let's draw the  dfa which doesn't accept binary string divisible by 2 I.e a string starting with 1. Now draw the complement of the dfa and you are done.

Comments

Thanks! But a binary string not divisible by 2 should end with 1 maybe you wanted to say that. I've seen about this at many other places and according to them the automata in figure (1) is correct. My question here is, if figure 1 is correct then it will accept all binary numbers divisible by 2 but, also, "It accepts NULL character which is not divisible by 2"

---

Null is always considered as multiple and divisible of any number

---

Thanks!

---

∈ is not a number , how can it be divisible by 2, ya 0 is divisible by everything but How ∈ ?

---

∈ means ‘nothing’. So when you divide ‘nothing’ with ‘something’, ‘nothing’ will remain, right?