55 votes 55 votes Let $L$ be the language represented by the regular expression $\Sigma^*0011\Sigma^*$ where $\Sigma = \{0, 1\}$. What is the minimum number of states in a DFA that recognizes $\bar{L}$ (complement of $L$)? $4$ $5$ $6$ $8$ Theory of Computation gatecse-2015-set3 theory-of-computation finite-automata normal minimal-state-automata + – go_editor asked Feb 14, 2015 edited Dec 18, 2018 by Rishi yadav go_editor 16.9k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply saxena0612 commented Dec 19, 2017 reply Follow Share Note: In this problem no need to draw NFA first and then minimize,instead try to draw DFA at first place it would be simple and solves the problem in less time ! 8 votes 8 votes Deepak Poonia commented Sep 11, 2023 reply Follow Share If $L$ is regular then $\overline{L}$ is also Regular. But if minimal DFA for $L$ has $k$ states then can we guarantee that minimal DFA for complement of $L$ will also have $k$ states?? The answer is YES. We can prove that if minimal DFA for a regular language $L$ has $n$ states then the minimal DFA for complement of $L$ will also have $n$ states. Detailed Video Explanation of this proof: https://youtu.be/3szxKVVUo1A 2 votes 2 votes Please log in or register to add a comment.
Best answer 64 votes 64 votes First we can draw dfa for $L$ which has $5$ states after that for $L$ compliment we will convert all final to non final and all non final to final so, total states is $5$. Anwer is option B. Anoop Sonkar answered Feb 15, 2015 edited Jun 15, 2018 by Milicevic3306 Anoop Sonkar comment Share Follow See all 27 Comments See all 27 27 Comments reply Vijay Dwivedi 1 commented May 18, 2015 reply Follow Share Can you please draw the dfa for this? 0 votes 0 votes Praveen Saini commented May 19, 2015 i edited Aug 9, 2015 reply Follow Share NFA for L = (0+1)*0011(0+1)* [ all strings that contain 0011 as substring] Convert NFA to DFA DFA for L = (0+1)*0011(0+1)* [ all strings that contain 0011 as substring] DFA for $\bar{L}$ (complement of L) that doesn't contain 0011 as subtring Note : No need to do this in such question DFA that contain substring having n length will have n+1 states and same with complement 80 votes 80 votes wxyz commented Dec 11, 2015 reply Follow Share hi praveen, how did u convert the above NFA to DFA? i am getting more numbers of states in DFA... :( 2 votes 2 votes Praveen Saini commented Dec 11, 2015 reply Follow Share few of them get minimized, look carefully at final states in table you get after NFA to DFA conversion I am sure final states will get minimized to one final state 10 votes 10 votes wxyz commented Dec 11, 2015 reply Follow Share yes u r correct..thank u..:) 0 votes 0 votes lifeisshubh commented Jan 31, 2017 reply Follow Share Aren't there only four final states in the DFA that are accepting L(bar) 1 votes 1 votes Regina Phalange commented Apr 13, 2017 reply Follow Share @lifeisshubh yes, right but total no of states required is 5 2 votes 2 votes nikkey123 commented Sep 3, 2017 reply Follow Share i am getting 6 states and 2 final states in DFA how do you convert it into dfa of 5 states. PLZ explain 0 votes 0 votes tarpitsahu commented Dec 9, 2017 reply Follow Share Is it mandatory to show dead state ? Shouldn't the answer be 4 (not considering the 5th state?) ? 0 votes 0 votes Praveen Saini commented Dec 13, 2017 reply Follow Share Yes, in DFA, we must have transition for each symbol on each state, $Q \times \Sigma \rightarrow Q $. 0 votes 0 votes habedo007 commented Dec 15, 2017 reply Follow Share @Praveen Saini sir Isn't it true that for an NFA with $n$ states we have its equivalent minimized DFA having $2^n$ states? Then shouldn't this NFA's DFA contain $2^5$ states? 0 votes 0 votes hs_yadav commented Dec 19, 2017 reply Follow Share @ habedo007 NFA(n-states) ->DFA(2n) ...it means it burst case DFA could have 2n not for always... 0 votes 0 votes Praveen Saini commented Dec 20, 2017 reply Follow Share @habed0007 No, it is maximum up to $2^n$ 3 votes 3 votes habedo007 commented Dec 22, 2017 reply Follow Share @Praveen Saini sir thank you for correcting me. 1 votes 1 votes reena_kandari commented Dec 26, 2017 reply Follow Share @ Praveen Saini sir, By using this method for complement of a language: To construct the DFA D that accepts the complement of L, simply convert each accepting state in A into a non-accepting state in D and convert each non-accepting state in A into an accept state in D. if DFA D is minimized then is it always guranteed that reversal of dfa D' will be also always minimized? 2 votes 2 votes Praveen Saini commented Dec 29, 2017 reply Follow Share Yes. 2 votes 2 votes saumya mishra commented Jun 6, 2018 reply Follow Share While converting nfa to dfa I am getting 8 states by using the conversion method of nfa to dfa. 0 votes 0 votes Karthik Selvam commented Nov 20, 2018 reply Follow Share Hi Praveen, If we minimize the Regular Expression (0+1)*0011(0+1)* it becomes (0+1)*0011 (R*R*=R*) and proceed. Is it necessary that we show transition on last state of NFA? 0 votes 0 votes Shubhgupta commented Dec 4, 2018 reply Follow Share @ Karthik Selvam, language containing 0011 as a substring is different from language ending with 0011. 1 votes 1 votes harendra singh commented Dec 18, 2018 reply Follow Share Yeah me too.. 0 votes 0 votes mrinmoyh commented Sep 16, 2019 reply Follow Share @Praveen Saini sir, Note : No need to do this in such question DFA that contain substring having n length will have n+1 states and same with complement Can I take it as a formula, which I can apply for all ??? 1 votes 1 votes Sid2971996 commented Oct 3, 2019 reply Follow Share Why aren't we optimizing? If we optimize, we would get 4 states. 0 votes 0 votes sandmuk754 commented Nov 21, 2019 reply Follow Share SIR I HAVE PROBLEM, AS U KNOW THERE IS RULE FOR CONVERTING NFA TO DFA ,BUT BY THAT PROCESS IF I MADE DFA THEN I GET 8 STATES . SIR PLZ HELP ME BY MAKING DFA BY THAT PROCESS 1 votes 1 votes aquagrl commented Sep 26, 2020 reply Follow Share the last state in L' is dead state, will that be also considered? But every dfa we make we ignore the dead state. 0 votes 0 votes Venky8 commented Dec 29, 2021 reply Follow Share Also read easy proof: https://stackoverflow.com/questions/57969207/if-a-dfa-is-minimized-is-it-guaranteed-that-its-complement-is-also-minimized 1 votes 1 votes priyanshumangal01 commented Jan 8, 2023 reply Follow Share I am also faci same prooblem..while converting given langauge in to nfa and then in to dfa, i am getting 8 states which is minmizd dfa... 0 votes 0 votes rhl commented Oct 29, 2023 reply Follow Share @aquagrl no we don't ignore dead state in minimal DFA instead we ignore unreachable states in minimal DFA. 1 votes 1 votes Please log in or register to add a comment.
16 votes 16 votes For any substring pattern we need n+1 states, where n is the cardinality of the substring i.e. |w|=n Here |0011|=4 . So we require 4+1=5 states Kalpataru Bose answered Apr 22, 2018 Kalpataru Bose comment Share Follow See 1 comment See all 1 1 comment reply Akhilesh Singla commented May 14, 2018 reply Follow Share Also mention that its complement will also require the same no. of states since the DFA is minimized. 2 votes 2 votes Please log in or register to add a comment.
1 votes 1 votes No. of states in DFA accepting L and complement of L is same. So let's draw minimal DFA for L, So, 5 states are there. varunrajarathnam answered Aug 23, 2020 varunrajarathnam comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes contain 5 state correct option B Dheeraj Kumar 1 answered Sep 17, 2019 Dheeraj Kumar 1 comment Share Follow See all 0 reply Please log in or register to add a comment.