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 AnilGoudar commented Apr 2, 2017 reply Follow Share Hi Akash, the DFA also accpets 8a's which is not in given language. 8a's is not in given language. 0 votes 0 votes GautamDas commented Apr 3, 2017 reply Follow Share Yeah, DFA will have 16 states. I have an idea to explain the construction. Let us see the multiples of 3 and 5 first. Multiples of 3: 3,6,9,12,15,18,21,24,27,30... Multiples of 5: 5,10,15,20,25,30... Now, if you observe multiples of both 3 and 5 are repeating after 15. For example, 18 = 15+3, 21 = 15 + 6 and 20 = 15 + 5, 25 = 15 + 10. Hence, we need 15 states excluding the initial state. So, the total state would be 16. 1 votes 1 votes Sourav_35 commented Jun 3, 2018 reply Follow Share This is not a DFA bcoz q3 on 'a' is going to both q0 and q4 0 votes 0 votes 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.