1 votes 1 votes Consider the regular language L=(00+0000)* . The minimum number of states in any DFA accepting this languages is? Theory of Computation finite-automata theory-of-computation minimal-state-automata + – iarnav asked Aug 18, 2017 iarnav 1.4k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply joshi_nitish commented Aug 18, 2017 reply Follow Share it is accepting all even length(including epsilon) strings over {0}*.. 2 states dfa is sufficient. 0 votes 0 votes iarnav commented Aug 18, 2017 reply Follow Share What if, the R.E would be (1+111)* 0 votes 0 votes joshi_nitish commented Aug 18, 2017 reply Follow Share if input alphabet, sigma = {1}, then (1+111)* will generate every string defined on sigma*, so only one state dfa is needed for this case. 1 votes 1 votes iarnav commented Aug 18, 2017 reply Follow Share You the best, actually I had some confusion after I did this Ques - R.E (111+11111)*, GATE 2006 Ques, that's kinda tricky! 0 votes 0 votes iarnav commented Aug 18, 2017 reply Follow Share @joshi_nitish please one more doubt - (11+111)* what will be the minimum states DFA can accept it? 0 votes 0 votes hs_yadav commented Aug 18, 2017 i edited by hs_yadav Aug 19, 2017 reply Follow Share i think..... (11+111)* is representing all string excluding (1)..... 0 votes 0 votes joshi_nitish commented Aug 18, 2017 reply Follow Share if sigma = {1} then minimum 3 states DFA is sufficient. 1 votes 1 votes iarnav commented Aug 18, 2017 reply Follow Share @Joshi Correct, thanks! 0 votes 0 votes Swapan commented Aug 18, 2017 reply Follow Share @joshi can you explain ? I thought it need 5 states 0 votes 0 votes suryansh rajput commented Aug 9, 2022 reply Follow Share this language is equivalent to L={even no. of 0’s} so, just requires 2 states only 0 votes 0 votes Please log in or register to add a comment.
–1 votes –1 votes Here L = (00+0000)* means L = {ε, 00, 0000, 000000, ......} Minimum no. of states for DFA = 4 dekabh answered Aug 18, 2017 dekabh comment Share Follow See all 2 Comments See all 2 2 Comments reply just_bhavana commented Aug 18, 2017 reply Follow Share 1 is not an input symbol here, the only input symbol is 0 1 votes 1 votes iarnav commented Aug 18, 2017 i edited by iarnav Aug 18, 2017 reply Follow Share EDIT: Yes, only input symbol is 0. 0 votes 0 votes Please log in or register to add a comment.