1 votes 1 votes 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? anjali007 asked Jan 6, 2019 anjali007 4.9k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Shubhgupta commented Jan 6, 2019 i edited by Shubhgupta Jan 6, 2019 reply Follow Share 6 states? (0 should be rejected right?) 0 votes 0 votes anjali007 commented Jan 6, 2019 reply Follow Share ya.. can u pls explain how? 0 votes 0 votes Shubhgupta commented Jan 6, 2019 reply Follow Share answer added. 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes 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 answered Jan 6, 2019 • selected Jan 7, 2019 by anjali007 Shubhgupta comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments Shubhgupta commented Jan 15, 2019 reply Follow Share yes approach is correct but 5 states will be q0,q1,q2,q3,q4 not q5. 0 votes 0 votes jatin khachane 1 commented Jan 15, 2019 reply Follow Share Ya tht was done in hurry 0 votes 0 votes bhanu kumar 1 commented Jan 15, 2019 reply Follow Share 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 1 votes 1 votes Please log in or register to add a comment.