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

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