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.3k 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.