46 46 votes The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____. Theory of Computation gatecse-2015-set2 theory-of-computation finite-automata normal numerical-answers minimal-state-automata + – go_editor 23.7k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
Best answer 71 71 votes All strings ending with $10$. So, we need $3$ states. From first state on $1$, we go to second state. From second state on $0$ we go to third state. From third state on $0$ we go to first state and on $1$ we go to second state. Only third state is final. L = (0+1)*10 Minimal DFA will be as follows: Arjun answered Feb 18, 2015 • edited May 6, 2019 by Pooja Khatri Arjun comment Share Follow See all 10 Comments 10 10 Comments reply Show 7 previous comments Karthik Kumar Mudr 1 commented Apr 4, 2018 reply Follow flag @Bikram Veteran when ever we convert nfa to dfa is it always we get minimal dfa.can anyone explain plz 0 0 replyShare Satbir commented Jul 25, 2019 reply Follow flag No.we have to further reduce the DFA (if possible) using myhill-nerode theorem or using concept of equivalence classes. 0 0 replyShare Arjun commented Jul 25, 2019 reply Follow flag Minimization of DFA -- standard algorithm exist in any TOC textbook. 0 0 replyShare Please log in or register to add a comment.
3 3 votes Make NFA from given R.E and then convert it to DFA, you'll get Arjun Sir's DFA and Answer as 3 states! iarnav answered Aug 23, 2017 iarnav comment Share Follow See all 7 Comments 7 7 Comments reply hem chandra joshi commented Nov 14, 2017 reply Follow flag I don't think so , plz draw the nfa and its conversion I am getting more than 3 states . 1 1 replyShare Puja Mishra commented Jan 14, 2018 reply Follow flag When u r answering any question ... give ur own views which will nt be same as other answers ...When u want to add point or doubt... comment under best answer .... where is the diagram of nfa u r suggesting .... vague explanation ... 1 1 replyShare James Bond commented Mar 13, 2018 reply Follow flag Puja Mishra i think you are not doing any productive work, i have seen a lot of similar comment from you, this comment is a part of guideline, if you are doing this for gaining points then it's of no use but irritating. I hope you don't post unnecessary video URLs also as it causes lots of scrolling, and why am i saying this because you post a lot of youtube urls irrespective of the content. i hope you refrain from this activity. you really don't answer any question, so please.. 6 6 replyShare iarnav commented Apr 4, 2018 reply Follow flag Right on, brother! 0 0 replyShare Lakshman Bhaiya commented Jan 14, 2019 i edited by Lakshman Bhaiya Jan 7, 2020 reply Follow flag see this is the actual procedure 15 15 replyShare Manoj Kumar Pandey commented Jan 7, 2020 reply Follow flag Your final dfa can't accept string 110 so wrong moves 1 1 replyShare Lakshman Bhaiya commented Jan 7, 2020 reply Follow flag Now it is corrected. 0 0 replyShare Please log in or register to add a comment.
2 2 votes atleast 3 states require to for this regular expresssion. . rohit37s answered Apr 12, 2015 rohit37s comment Share Follow See 1 comment 1 1 comment reply jugnu1337 commented Jan 10, 2022 reply Follow flag why we cant use dead state… and when we will use it. i am little bit confuse, some time when ques. ask for minimal dfa we use it and sometime not, pls tell me when we use dead state and when not 0 0 replyShare Please log in or register to add a comment.
2 2 votes Minimun number of states req. by DFA = 3 Harshit2021 answered Aug 14, 2021 Harshit2021 comment Share Follow 0 reply Please log in or register to add a comment.
0 0 votes No. of states in minimal DFA is 3. varunrajarathnam answered Aug 23, 2020 varunrajarathnam comment Share Follow 0 reply Please log in or register to add a comment.
0 0 votes make NFA, then convert to DFA, simply see 3 states, you cannot reduce it further shashankrustagi answered Jan 17, 2021 shashankrustagi comment Share Follow 0 reply Please log in or register to add a comment.
