0 votes 0 votes Select the regular languages from a list of given languages: 1)Strings over alphabet {0,1,2,3...9} where final digit has not appeared before. 2)strings that contain substring of the form wcw where w belongs to {0,1}+ and c belongs to {0,1}* Theory of Computation theory-of-computation regular-language + – jenny101 asked Dec 6, 2016 retagged Jun 4, 2017 by Arjun jenny101 1.7k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 4 votes 4 votes 1) is regular , $(1+2+3+.............+9)^*0+(0+2+3+.............+9)^*1+(0+1+3+.............+9)^*2+...................(0+1+2+3+.............+8)^*9+\epsilon$ NFA of this string contain 12 states. Min no of states in eqv DFA = [ ? ] // If anyone knows, please edit here with logic. 2)is CSL, The Language generated by the grammer is $w(0+1)^*w$ So, it generates={00,11,0101,01000001...........................} srestha answered Dec 6, 2016 selected Dec 7, 2016 by vijaycs srestha comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments srestha commented Dec 7, 2016 reply Follow Share yes, multiple initial state not possible for DFA. So, what can we do, just $\epsilon$ moves to next state. try with small input like (1,2,3) 0 votes 0 votes Kapil commented Dec 7, 2016 reply Follow Share @vijaycs NFA is having 12 states with 10 epsilon transitions from the first state and 10 loops and also last 10 transitions towards final state. But, converting to DFA is very lengthy as you know it requires closure property to be used and we need to remove 10 epsilon transitions. 1 votes 1 votes vijaycs commented Dec 7, 2016 reply Follow Share Yes, Correct. So we do not expect gate will ask any such lengthy question.. Thanks Kapil : ) 1 votes 1 votes Please log in or register to add a comment.