#Self doubt

Question

Answer 1

for binary string the value to be divisible by :

4 will have 3 states.

5 will have 5 states.

so minimum states will be gcd(3,5) which is equal to 1 so we multiply the number of states in this case.

15 states.

 

Comments

Why #states in case of divisible by 4 is 3?? It should be 4, no? For remainder 0,1,2,3.

---

Yes divisible by 4 we need 4 state

---

Answer should be 20

---

Yeah.

---

@aambazinga because when we construct the dfa it has 4 states. which can be minimised to 3 as two states apart from initial and final will be equal. so we will have 3states.

---

@abhishek bro it says about the divisibility of the binary string not the number of symbols... means we will make dfa for {0,100,1000,1100.... }

---

@arvin

I'm honestly not getting what you are trying to do and say.

Please elaborate

---

@arvin,

GCD formula used when ( d1 is divisible by d2 or d2 is divisible by d1 ) and the connector is or

here d1 = 4 and d2 =5 ===> can't use GCD formula, use LCM formula ===> you can get 20 states..

 

so minimum states will be gcd(3,5)

then result is 1, right? 

---

@shaik masthan see now i updated. i forgot something. and did u got how dfa has 3 states.

---

@aambazinga i dont think u are minimising the dfa which will have 3 states.

---

Ok yeah, Q1,Q3 turns out to be equivalent states.

---

how Q1Q3 in one state?

There will be 20 states

---

@srestha if we make a dfa than it gets reduced to 3 states.

---

@srestha, @arvin is right... I too had that confusion , but when I applied minimization, they actually come out to be equivalent states.

 

And this is true to do because we require to check divisibility only, but not to find modulus.

---

@aambazinga it has a formula : when binary string is divisible by a value 2^k . than we get (k+1) states.

---

@arvin, bhai please give reference to any book or lecture where you learmed that.. I usually stuck in these kind of questions.

---

it was taught to us last year

there are three case :

1) when divided by a factor of 2^k : states k+1

2) when divided by odd number (k) : states K

3)when divided by even number not equal to 2^k : divide  the number by 2 unless an odd number comes and than add odd remaining value +no. of division

eg : divided by 20 : 20/2 = 10 : 10/2 = 5 --> 5+1+1 states

---

@ arvin, Sorry BRO....

Yes you are right.... I forget that it is a Binary Number.... i mistakenly assume it is decimal number..

i am really sorry bro... i wasted so much of your time.

Thanks @Srestha Mam, For responding on this question on my request

---

@shaik masthan : its ok bro i am here too to make mistakes and learn. dont worry :)

---

@arvin Can u plz draw the minimized DFA

I still doubt, is that formula correct?

---

I tried divisible by 2 or 3 and got ans 6

---

@srestha you can check it now :p :)

---

when we divide by 2 we will get 2 as per formula :2^k =k+1

2^1 : means : 1+1 = 2 state

---

@arvin ok :)

See then minimized DFA for mod5

it has 4 states

$a_{0},a_{2},\left \{ a_{1}a_{3} \right \},a_{4}$

right?

---

no mam @srestha its asking for binary values which is {0000,0101,1010,1111.......................}

i think you are getting it wrong. u dont worry about the formulae they have been tested.

---

where wrong? See I drawn the table

---

no mam these two states wont be equal do this by calculating 0equi , 1equi, 2equi.... u can prove this.

---

yes, it have 5 states

not 4