Applied Course Test 1

Question

The number of states in a minimal DFA that accepts set of all strings beginning with 1 that, when interpreted as a binary integer is a multiple of 5 over the alphabet={0,1}. For example, strings 101, 1010 and 1111 are in the language?

Comments

6 states? (0 should be rejected right?)

---

ya.. can u pls explain how?

---

answer added.

Answer 1

Make DFA for divisible by 5 and exclude '0' string from that DFA  So based on this minimal DFA will have 7 states and looks like below-

Approach is-

in divisible by 5 DFA there will be 5 equivalence classes{0,1,2,3,4} and as mentioned in question strings are start with 1 so we need to reject all string with 0.

Comments

yes approach is correct but 5 states will be q0,q1,q2,q3,q4 not q5.

---

Ya tht was done in hurry

---

is This Logic Right or Not?

        we know modulo 5 DFA need  minimum 5 state, in this all state work in cycle with each other state.

Here 0 is not start point means we have to reject it so 1 extra state for it and also State 0 is not doing its work so we  need 1 Extra state for it to do the job of it.

 so total    5+1+1=7