25 votes 25 votes We require a four state automaton to recognize the regular expression $(a\mid b)^*abb$ Give an NFA for this purpose Give a DFA for this purpose Theory of Computation gatecse-2002 theory-of-computation finite-automata normal descriptive + – Kathleen asked Sep 15, 2014 edited May 15, 2018 by Milicevic3306 Kathleen 4.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 37 votes 37 votes NFA for regular expression $(a+b)^*abb$ and its equivalent $\textsf{DFA}$ will be as follows: Praveen Saini answered Mar 9, 2015 edited May 31, 2021 by Arjun Praveen Saini comment Share Follow See all 12 Comments See all 12 12 Comments reply Prajwal Bhat commented Nov 17, 2016 reply Follow Share @Praveen Saini Sir What is the meaning of (a/b)* the question,is it (a+b)* what they have meant? 1 votes 1 votes Praveen Saini commented Nov 17, 2016 reply Follow Share yes, afai think 1 votes 1 votes talha hashim commented Sep 6, 2018 reply Follow Share praveen sir u r the best toc expert ever i seen 1 votes 1 votes shraddha priya commented Oct 28, 2018 reply Follow Share state a b qo q0q1 q0 q1 ^ q2 q2 ^ q3 q3 ^ ^ q0q1 q0q1 q0q2 q0q2 q0q1 q0q3 q0q3 q0q1 q0 q3 is final state so q0q3 also final state. Total 6 states. Where am I going wrong? Pls help @Praveen Saini 1 votes 1 votes Shubhgupta commented Dec 4, 2018 reply Follow Share @shraddha priya , there is no need of q1, q2 and q3 check once. 1 votes 1 votes air1ankit commented Dec 12, 2018 reply Follow Share @Praveen Saini sir construct an NFA for regular expression (a+b)* abb and then convert it into DFA, will that be okk sir ?? 0 votes 0 votes Lakshman Bhaiya commented Jan 13, 2019 reply Follow Share Yes, this is good, but it is a time-consuming process, we can make DFA from the regular expression. 0 votes 0 votes ayushsomani commented Jun 19, 2019 reply Follow Share How you will make DFA directly? 0 votes 0 votes Satbir commented Jul 25, 2019 reply Follow Share it comes from practise 0 votes 0 votes svas7246 commented Jun 26, 2021 reply Follow Share @Praveen Saini for The DFA here there is (a+b)∗ theres is an expression for b but how is it justified for a* 0 votes 0 votes Aman Lakher commented Dec 27, 2021 reply Follow Share in option A ,this NFA is for end with abb. in option B, we can directly draw dfa for end with abb. if we convert nfa to dfa , it will take much time. 0 votes 0 votes ꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂ commented Oct 15, 2023 reply Follow Share @svas7246As u can see clearly atleast one a and 2 b’s are required to accept the string so if first a comes it goes to q1 state and after that any number of a comes it will remain same in q1 state and after that when 2 b’s comes it goes to final state. 0 votes 0 votes Please log in or register to add a comment.