0 votes 0 votes Minimum states required for DFA that accepts : L = {w1 x w2 | w,x belongs to {a,b}* | w1 >= 0, w2 > 1 and x >= 0 }. Theory of Computation theory-of-computation minimal-state-automata number-of-states + – Na462 asked Sep 10, 2018 Na462 941 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply arvin commented Sep 10, 2018 reply Follow Share 3. 0 votes 0 votes ad140 commented Sep 10, 2018 reply Follow Share a*a*a+ = a+ i.e the form will be (a+b)^+ 0 votes 0 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes we have, L = {w1 x w2 | w,x belongs to {a,b}* | w1 >= 0, w2 > 1 and x >= 0 }. means regular expression for L = (a+b)* (a+b)* (a+b)2(a+b)* =set of strings having length atleast 2. so number of states in minimal DFA = 3 states. arvin answered Sep 10, 2018 selected Sep 10, 2018 by Na462 arvin comment Share Follow See all 11 Comments See all 11 11 Comments reply Na462 commented Sep 10, 2018 reply Follow Share Brother i can substitute w1 as epsilon w2 as say (a+b) and x as also epsilon. So according to it the minimum length string should be 1. What is wrong here ? 0 votes 0 votes ad140 commented Sep 10, 2018 reply Follow Share Yes so states would be 2. 0 votes 0 votes arvin commented Sep 10, 2018 reply Follow Share @na46a the question says w2>1 means size of w2>= 2symbols. 0 votes 0 votes ad140 commented Sep 10, 2018 reply Follow Share (a+b)^+ Yes you are correct. 0 votes 0 votes arvin commented Sep 10, 2018 reply Follow Share @ad140 see the question once again it would be (a+b)2(a+b)* 0 votes 0 votes ad140 commented Sep 10, 2018 reply Follow Share Yes I didn't see >1 I saw it as >=1 so it will be >=2 so there will be three states. I had done a similar mistake in my sessionals too. 0 votes 0 votes Na462 commented Sep 10, 2018 reply Follow Share Ohk i got it so w2 i can take as (a+b)^2 so if i take minimum value of every Expression so w1 = epsilon , w2 is (a+b)^2 and x = epsilon so minimum string will be of length 2 or i could take w1 = (a+b)* , w2 = (a+b) and x as epsilon so L = (a+b)*(a+b)^2. Hence total 3 states am i right ? 0 votes 0 votes ad140 commented Sep 10, 2018 reply Follow Share Yes 0 votes 0 votes arvin commented Sep 10, 2018 reply Follow Share @ad140 @na462 yes now u got that. :) 0 votes 0 votes Shaik Masthan commented Sep 10, 2018 reply Follow Share @Na462 it's your responsibility, to select as BEST if you are satisfied with the answer 1 votes 1 votes arvin commented Sep 10, 2018 reply Follow Share @shaikh :p 0 votes 0 votes Please log in or register to add a comment.