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.8k 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 Arjun commented Mar 3, 2015 reply Follow Share ^ in regular expression is for? 0 votes 0 votes Praveen Saini commented Mar 3, 2015 reply Follow Share That is epsilon 0 votes 0 votes Prateek kumar commented Aug 23, 2016 reply Follow Share @Pravenn Sir how did you get regular expression by Arden's THM ? 0 votes 0 votes Praveen Saini commented Aug 23, 2016 reply Follow Share q0= ep + q1a + q2a q1=q0b , q2 = q1b =q0bb. , put value of q1 and q2 in first. you will get q0 , then find q1 and q2 regular expression = q0 + q1 +q2 0 votes 0 votes Sambit Kumar commented Aug 24, 2016 reply Follow Share can regular expression be: (a*(b+ ϵ )(b+ ϵ )aa*)* (b+ ϵ )(b+ ϵ ) 1 votes 1 votes Vishal Goyal commented Jul 4, 2017 reply Follow Share regular expression (a+ba+bba)*(ϵ+b+bb) any other easy way to write regular expressions for the given dfa because using Arden's theorem its difficult and reqires lots of patience if anyone can share easier way to do this whould be helpful :) 1 votes 1 votes Hemant Parihar commented Jul 6, 2017 reply Follow Share @vishal You can use state elimination method to find the regular expression for a given dfa. It is given in peter linz and also many other books. 4 votes 4 votes BillyFitt commented Aug 8, 2017 i moved by Hira Thakur Feb 6, 2023 reply Follow Share Hi! I have one question - what happens if I want only 3 consecutive occurrences of the letter b to be accepted? I mean bbb and aabbbaaabbbb should be okey, but aabbbbab shouldnt. I think something in q3 must be changed, in order to work, but I dont know what. Would be very nice if you could help me :) Thanks! –2 votes –2 votes Gate Ranker18 commented Aug 30, 2017 reply Follow Share BillyFitt this is regular expression for ur query : a*ba*ba*ba* 0 votes 0 votes set2018 commented Oct 26, 2017 reply Follow Share Hemant Parihar will u pls share state elimination diagram 0 votes 0 votes lakshaysaini2013 commented Nov 21, 2018 reply Follow Share "q0= ep + q1a + q2a " sir if we put the value we will get q0 = ep+q0ba+q0bba => q0 = ep+q0(ba+bba) so we have r=q+rp as r = qp* than q0 = ep(ba+bba)* = (ba+bba)* as RE is q0+q1+q2 => q0+q0b+q0bb => q0(ep+b+bb) so final RE is (ba+bba)* (ep+b+bb) but your ans doesn't match i think we the q0 expression will be q0= ep + q1a + q2a +q0a because we have incoming edge from q0 itself too then final RE is (a+ba+bba)* (ep+b+bb) 0 votes 0 votes Shubhm commented Jul 1, 2019 reply Follow Share what would be the corresponding NFA? 0 votes 0 votes chandra sai commented Sep 6, 2019 reply Follow Share Can anyone give Finite state Diagram for binary subtractor..thanks in advance 0 votes 0 votes 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 Show 7 previous comments 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.