4,923 views
6 votes
6 votes
Number of states in DFA which accepts the binary strings divisible by 4 or 5.
answer?

4 Answers

Best answer
12 votes
12 votes

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

I think, It is 20 states. 

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

0 votes
0 votes

Let me know if I'm wrong 

0 votes
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
0 votes
1 answer
2
Lakshman Bhaiya asked Dec 27, 2018
543 views
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�...
1 votes
1 votes
2 answers
3
Shivani gaikawad asked Jun 5, 2018
916 views
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
0 votes
0 votes
2 answers
4
Shivani gaikawad asked Jun 5, 2018
437 views
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