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 998 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.