1 votes 1 votes What will be the number of non-final states in the minimal DFA for the language L = { the set of strings over alphabet (a.b) containing at least three occurrences of 3 consecutive b’s, overlapping permitted} Theory of Computation testbook-test-series number-of-dfa finite-automata + – Rajat Agrawal007 asked Nov 18, 2021 Rajat Agrawal007 2.2k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Chandrabhan Vishwa 1 commented Nov 19, 2021 reply Follow Share ans is 9 0 votes 0 votes Kshitij-Kumre commented Nov 24, 2021 reply Follow Share how? 0 votes 0 votes girish13 commented Dec 3, 2021 reply Follow Share Please checkout this answer https://gateoverflow.in/365921/Testbook-test-series?show=366602#a366602 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes DFA for the language L = {the set of strings over the alphabet {a, b} containing at least three occurrences of three consecutive b's, overlapping permitted} For any Finite Automata question, we should always try writing some strings which belongs to the language, which will give us clear picture about how to proceed on DFA construction. Some important observations about the above DFA: The state 4 in the above DFA indicates that we have seen our 1st occurrence of 3 consecutive b’s, state 7 in the above DFA indicates that we have seen our 2nd occurrence of 3 consecutive b’s and state 10 in the above DFA indicates that we have seen our 3rd occurrence of 3 consecutive b’s which is the final state. If the string is bbbbb, then we go through states 1,2,3,4,7,10. Here, the three occurences of b’s are overlapped. If the string is bbbabbbb, then we through states 1,2,3,4,5,6,7,10. The states 5 and 6 are used to handle any a’s that break the sequence of 2nd occurrence 3 consecutive b’s. Similarly, if the string is bbbbabbb, then we through states 1,2,3,4,7,8,9,10. The states 8 and 9 are used to handle any a’s that break the sequence of 3rd occurrence 3 consecutive b’s. girish13 answered Dec 2, 2021 edited Dec 3, 2021 by girish13 girish13 comment Share Follow See 1 comment See all 1 1 comment reply ramakrushna commented Dec 18, 2021 reply Follow Share Please check your answer as its accepting a string bbbbabb. That means 2-consecutive b’s are also accepting so not satisfying the required language. The Answer should be 12. Check the below snip its accepting all the language including the one i have mentioned for your provided DFA. q0 to q11. total 12 states required. The analysis done by @girish13 is fully correct. So attaching only the DFA one. Hope it helps. 0 votes 0 votes Please log in or register to add a comment.