2 votes 2 votes Construct minimal DFA for L = {an: n is either a multiple of three or a multiple of 5 } Theory of Computation theory-of-computation finite-automata + – Vicky rix asked Apr 2, 2017 retagged Jun 4, 2017 by Arjun Vicky rix 4.8k views answer comment Share Follow See 1 comment See all 1 1 comment reply JAINchiNMay commented Oct 3, 2020 reply Follow Share @Prateek Raghuvanshi i think empty string should not be accepted but your answer is accepting it 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes In minimized dfa 15 states will be present, because lcm(3,5)=15 so loop should be of 15. Prateek Raghuvanshi answered Jun 3, 2018 Prateek Raghuvanshi comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Gate Fever commented Oct 17, 2018 reply Follow Share yes , it can be done in 15 states!! 0 votes 0 votes goxul commented Oct 15, 2019 reply Follow Share This is incorrect, as the language is (a,b). The b transitions are missing. 0 votes 0 votes Satbir commented Oct 15, 2019 reply Follow Share This is incorrect, as the language is (a,b). The b transitions are missing. where is it written that language has strings (a,b) ? 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes DFA with 16 states. Note: I think it can be minimised. I have done by constructing NFA and then converting NFA to DFA. AnilGoudar answered Apr 2, 2017 AnilGoudar comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Sourav_35 commented Jun 3, 2018 i edited by Sourav_35 Jun 3, 2018 reply Follow Share By applying your logic then will the number of states in dfa for a^n such that n is a multiple of 3 or 7 be 22? If that be the case then this kind of problems could be solved by a simple trick: If L=a^n such that n is a multiple of x or y then number of states in dfa accepting L would be (x*y)+1 provided x doesn't divides y if x<y and vice-versa Am I correct? 0 votes 0 votes abhishekmehta4u commented Jun 3, 2018 reply Follow Share No , answer is wrong 9 state are required. 0 votes 0 votes Sourav_35 commented Jun 3, 2018 reply Follow Share No you are wrong...a11,a13,a14....all will be accepted but these are neither multiple of 3 nor 5 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Number of states =16 shreya_30 answered May 9, 2023 shreya_30 comment Share Follow See all 0 reply Please log in or register to add a comment.