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.
@Shubhgupta ur dfa is accepting the strings that are starting with zero.. u should add a dead state transition for zero from q0.... so the no of states will be 7 as said by you earlier.. can u plz explain what procedure did u follow for the states q1,q3,q2,q4,q5..
@anjali007, i have previously added that dead state but it doesn't make more sense because if a string 0101 then its binary equivalent is 5 right? but i think as mentioned in question DFA accepts stating with 1 only.
Correct image added.
@Shubhgupta and for the rest of the five states did u follow any "particular approach" or just analysed the states?
@anjali007, as i mentioned in answer q1 represents string with 1 remainder, q2 with 2 remainder, q3 with 3 remainder and q4 with 4 remainder. and i have created qf new because we don't want to accept 0.
is it clear?
@Shubhgupta
Please check if this is the apporach you used
first considering : Integer of binary string as multiple of 5 ==> 5 states q0,q1,q2,q3,q4
0 1
-->*q0 q0 q1
q1 q2 q3
q2 q4 q0
q3 q1 q2
q4 q3 q4
Now we have to ignore strings starting with one hence after modification of transitions we get dfa as in selected and
if starting with 1 condition not mentioned then it will '6' states right??
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
64.3k questions
77.9k answers
244k comments
80.0k users