Log In
5 votes
Number of states in DFA which accepts the binary strings divisible by 4 or 5.
in Theory of Computation 1.4k views
I'm getting 3 states.
given answer is 5
I think 20 states are needed
It is 7.
@rohit can u post the picture and how did u derive it?

4 Answers

12 votes
Best answer

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.

selected by

@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 ??

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

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

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
3 votes

I think, It is 20 states. 

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

sorry i took a wrong example. am checking ur dfa

i could only draw nfa. dfa is getting very big

Displaying WP_20161209_001.jpg

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

Let me know if I'm wrong 

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.
0 votes
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.

Related questions

0 votes
1 answer
Construct a minimal DFA which accepts set of all strings over {a,b}, such that $1)$Second symbol from $RHS$ should be $‘a’$ $2)$Third symbol from $RHS$ should be $‘a’$
asked Dec 27, 2018 in Theory of Computation Lakshman Patel RJIT 105 views
0 votes
2 answers
The minimum number of state in the DFA for the language $L = \{ w \mid (n_a(w)+2n_b(w))mod \hspace{0.1cm} 3<2 \} $ is
asked Jun 5, 2018 in Theory of Computation Shivani gaikawad 248 views
0 votes
2 answers
The minimum number of state in the DFA for the language $L = \{ w \mid w \in \{a,b\}^* \text{ w has exactly two a's and at least two b's} \}$ is $9$ $10$ $16$ None
asked Jun 5, 2018 in Theory of Computation Shivani gaikawad 108 views
2 votes
1 answer
Minimum number of states in DFA where:, Number of a's and Number of b's are even and epsilon is not accepted.Langugae is defined over {a,b}
asked Nov 9, 2017 in Theory of Computation rahul sharma 5 262 views