32 votes 32 votes Draw the state transition of a deterministic finite state automaton which accepts all strings from the alphabet $\{a,b\}$, such that no string has $3$ consecutive occurrences of the letter $b$. Theory of Computation gate1993 theory-of-computation finite-automata easy descriptive + – Kathleen asked Sep 29, 2014 • recategorized Apr 22, 2021 by Lakshman Bhaiya Kathleen 12.9k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 58 votes 58 votes Design a DFA that accepts all strings contain $bbb$ regular expression $(a+b)^*bbb(a+b)^*$ then take complement of DFA such that no string has $3$ consecutive occurrences of the letter $b$. having regular expression $(a+ba+bba)^*(\epsilon + b+ bb)$ Praveen Saini answered Mar 3, 2015 • edited Feb 9, 2018 by kenzou Praveen Saini comment Share Follow See all 16 Comments See all 16 16 Comments reply Show 13 previous comments pritishc commented Dec 8, 2019 reply Follow Share Does the regular expression $(a + ab + abb)*$ work for this question? 0 votes 0 votes Shiva Sagar Rao commented Jan 30, 2021 reply Follow Share @pritishc $b$, $bb$ strings are not generated by your regular expression. 0 votes 0 votes raja11sep commented Jul 1, 2021 reply Follow Share @pritishc it will generate all strings starting with ‘a’ including epsilon. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes This is the approach for solving the given question:- Aditi0103 answered Jul 20, 2020 Aditi0103 comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes a*((ba+)+(bba+))* Aravind answered Oct 18, 2014 Aravind comment Share Follow See 1 comment See all 1 1 comment reply raja11sep commented Jul 1, 2021 reply Follow Share b, bb these strings are also part of the language which will not be generated by your regular expression. 0 votes 0 votes Please log in or register to add a comment.
–3 votes –3 votes In this ,firstly make the dfa of the language which accept all strings from the alphabet (a,b) such that all string contain three consecutive occurrence of the letter b ,then make non final state as final state and final state as non final,initial state will remain same then it become the dfa that accept all string not containing three consecutive b's. neha pawar answered Oct 18, 2014 neha pawar comment Share Follow See all 10 Comments See all 10 10 Comments reply Arjun commented Oct 18, 2014 reply Follow Share Idea is perfect. But the transitions for 'a' seems wrong. The first DFA accepts ababab rt? 1 votes 1 votes Tendua commented Oct 19, 2014 reply Follow Share 4 stage is a trap state 0 votes 0 votes Arjun commented Oct 19, 2014 reply Follow Share From state 2, a transition should go to state 1 rt? 0 votes 0 votes neha pawar commented Oct 20, 2014 i edited by Akash Kanase Dec 24, 2015 reply Follow Share yeah i have done mistake..sorry for that..if we make transition for 'a' on state q1 and q2 to state q0 then i think it will be correct dfa 2 votes 2 votes set2018 commented Aug 2, 2017 reply Follow Share whts wrong with this dfa ? @Bikram sir i also got same 0 votes 0 votes Bikram commented Aug 2, 2017 reply Follow Share @ set2018 From state 2 there must be a transition towards state 1, which is missing in this DFA. Tht's why it is not correct. 0 votes 0 votes Pritam Dutta commented Dec 13, 2017 reply Follow Share This DFA is for the language accepting strings with less than 3 'b' s . But here they are asking for strings with no 3 consecutive 'b' s . 1 votes 1 votes Pritam Dutta commented Dec 13, 2017 reply Follow Share See how your DFA even rejecting abaababab just bcoz it has more than 3 'b' s. But acc to the question it should be accepted . Hope this helps . 2 votes 2 votes Rajesh Panwar commented Dec 8, 2018 reply Follow Share check for string "abbaabba" it also accepted by dfa. 0 votes 0 votes raja11sep commented Jul 1, 2021 reply Follow Share The first DFA will accept all strings containing at least 3 ‘b’ s. The second DFA will accept all strings containing less than 3 ‘b’ s. 0 votes 0 votes Please log in or register to add a comment.