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 Show 24 previous comments 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.