TOC- DFA

Question

Number of states in DFA which accepts the binary strings divisible by 4 or 5.
answer?

Comments

I think 20 states are needed

---

It is 7.

---

@rohit can u post the picture and how did u derive it?

Answer 1

Divisible By 4

Divisible By 5

Now,use Cross product along with Union. DFA which accepts the binary strings divisible by 4 or 5 

This is very confusing DFA, but that's it . 13 states with 5 Final states.

Comments

@Kapil  ,  I have got one doubt here... 

Actually when we find cross product we are doing intersection of two languages , right ? In that case the DFA should have to be " Divisible by 4 AND Divisible by 5 " 
But here here we are getting " Divisible by 4 OR divisible by 5 "
Can you pls explain this part a bit..  Inspite of taking cross product we are able to get union of two languages ?

Is my understadning correct about compound automata ?

---

No,Kapil is doing union of the two languages not intersection ,so we get many final states.

---

@Kapil, How long it took you to come up with this solution ( I mean diagram and ans =13 states) ? Because it took me around 1 hr to verify your diagram. After seeing your first diagram ( divisibility by 4), I got that my solution of having 20 states was wrong and thought it must be having 15 or less state.But again, this less than 15 was putting me in trouble. But then finally got  that we can merge three states(X0Y0,  X1Y0, X2Y0) to one state (X0Y0).

Actually, I had forgotten this cross-product, union rule. :P

By the way, Thanks a lot. : )

  Please tell some intuition, if it took you less than 3-4 min ??

---

@vijaycs
Cross Product Explanation is Here .  Yeah you need to explain how to got that final diagram a bit, kapil :D

---

Thanks @pC : )

---

@vijaycs @pC

Cross product of two DFA gives the compound automata.

So, we can go in either direction to find union ( Final state comes whenever X0 comes or Y0 comes ) or intersection ( Final state comes whenever both X0 and Y0 come together )

I took me around 10 minutes , but to make a diagram online, it took much time as I was afraid :)

But, I guess GATE will never attempt to provide such Q.

(They will go for divisible 2 or 3)  OR (divisible by 8 or 16 - Here, no need to solve, just logically we have 8 states)

---

PS: The whole transition table that I made is very horrible, just like my handwriting :P, so its a risk if I upload that here :) 

---

Now, see my horrible diagram : P 

Actually, I was making this just by seeing first two DFA( div by 4 and div by 5). without making transition table. 

And then, After seeing your diagram, I got that we can merge three states ( states of the first column).

---

oops !! :P :D

Even Kirchoff's Rule will fail here :)

---

@kapil cound u plz explain my doubt on top..
ie Inspite of taking cross product we are able to get union of two languages ?

---

@pC only final states changes in case of union and intersection....like if it is divisible by 2 and 3 then states satisfying both the conditions together will be the final states ...
if it is divisible by 2 or 3 then even if one condition is satisfied then that state will be the final one...

---

@Kapil SIR , mod n machine will have n states like wise in your Divisible by 4 Machine shoudn't it have 4 states ? 

---

@gokou....we can merge one state here for getting minimal dfa...its nt a rule that if divisble by 4 then there will be 4 states..dont follow such things..even divisible by 8 will have 4 states after minimising the dfa..

---

@pC

Cross product is an approach to get Compound Automata.

But that does not always guarantees intersection. We need to check condition given in the question, i.e OR or AND . If it is OR like in this case, then Union is better to accept {0,4,5,8,10,12,15,16,20............}

and if AND is given, then intersection is better to accept {0,20,40,60,80,100,120,140.........}.

---

@sudhso @kapil

I always thought compound atomata always results in Intersection of two languages . Now I got my mistake .

So in the above diagram.  If we select final state as X0YO only then the above DFA Will Result in
binary strings divisible by 4 AND 5 , right ?

---

@vijaycs I solved it upto here . It will take less than 10 min .   But to draw the diagram will take much time :D And I become confused about AND and OR condition

---

yes @pC....

---

@Pc,why have u combined M and O??

x0y4 ->one is final and other is non-final

and X2y4 ->both are fnon-final

---

http://www.techtud.com/short-answer-question/binary-string-x-a0a1 ·-·-·-an−1n

Given answer is 5 here

---

@Mahima

Where is it written $5$ ?

---

@Kapil In the above link, number of minimum states in FA is asked (minimum 5 states in NFA) and here it is DFA. I got it now, thanks (y)

---

What  would be the answer if nfa is asked instead of dfa

Answer 2

I think, It is 20 states. 

If anyone finds optimized DFA with less than 20 states, please let us know. 

Comments

sorry i took a wrong example. am checking ur dfa

---

i could only draw nfa. dfa is getting very big

---

Yes im  also getting 20 states..  Could some experts confirm it ?

Answer 3

Let me know if I'm wrong 

Comments

1111 is 15. which is divisible by 5. is not accepted by ur machine

---

Yes. Right we need to modify dfa accepting mod4 number of 1s as well then. Thanks.

Answer 4

It will take 20 states.

 using cross product method we can implement AND and OR operations

 

Divisible by 4 ={q0,q1,q2,q3} q3 final state

Divisible by 5 ={w0,w1,w2,w3,w4} w4 final state

 

4x5 ={q0w0,q0w1,.....q3w3}

20 states.

To implement OR we need to make final states of all the states which have either q3 or w4 in them.