2 votes 2 votes iita asked Feb 4, 2017 iita 1.7k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments iita commented Feb 4, 2017 reply Follow Share my doubt is why can't L3 be regular as 0 ϵ (a,b)* so it is of the form WxWR which is regular...correct me if I am wrong 0 votes 0 votes saurabh rai commented Feb 4, 2017 reply Follow Share where it is given 0 ϵ (a,b)* ?? 0 votes 0 votes iita commented Feb 4, 2017 reply Follow Share look in L3 it's given that 0,W ϵ (a,b)*. ..... 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes L1,L2,L3 is CFL only L4 is regular Ritesh Singh answered Feb 4, 2017 Ritesh Singh comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes L1 DCFL L2 DCFL L3 DCFL L4 REGULAR **AFTER CORRECTIONS Smriti012 answered Feb 4, 2017 edited Feb 4, 2017 by Smriti012 Smriti012 comment Share Follow See all 7 Comments See all 7 7 Comments reply saurabh rai commented Feb 4, 2017 reply Follow Share how L3 is regular? 0 votes 0 votes Ritesh Singh commented Feb 4, 2017 reply Follow Share L3 is non regular... it is not in pattern of WxWR take an eg of WxWR ... abbba in which we assume a as W and last a as W^r and whole of string between them as X but the above question is like ab0ba and it is not mentioned that X is any combination of 0,a,b here we cannot take only a as W but to whole ab and reverse it in Wr 1 votes 1 votes Smriti012 commented Feb 4, 2017 reply Follow Share yes, L3 IS ALSO NOT REGULAR because alphabet set contains a,b,0... if it would have a,b only it would have been regular.... L3 (GIVEN alphabet set contains a,b,0) : STRING W . 0 . STRING WR (dcfl) L3 (ASSUMPTION WITH alphabet set contains a,b) : a(a+b)* a + b(a+b)* b (reg) @ritesh @saurabh Am I right now?? 0 votes 0 votes iita commented Feb 5, 2017 reply Follow Share but @smriti012 L3 contains alphabet set a,b,0 it true but...0 ϵ (a,b)* means we are free to take 0 as any srting so for e.g let's take a string abb0bba this the string generated by L3 so since, 0 ϵ (a,b) so we can assume that 0 will eat up everything except first and last letter abb0bba this part is 0 so it's a string which starts and ends with the same letter which is regular like, WxWR , x ϵ (a,b) this is regular language instead of x there is 0, 0 ϵ (a,b) ...make me correct if I am mistaken...??? 0 votes 0 votes Smriti012 commented Feb 5, 2017 reply Follow Share WxWR | w,x ϵ (a,b)* this is regular language (true) whereas W0WR | 0 could not ϵ (a,b)* ,w ϵ (a,b)* with alphabet set a,b,0 ...so this is CFL example : WxWR | w,x ϵ (0,1)* this is regular language { 1(0+1)* 1 + 0(0+1)* 0 : regular expression} whereas W2WR | 2 ,w ϵ (0,1)* with alphabet set 0,1,2............... if this is regular write regular expression for this!?????? As per my knowledge, its impossible to use alphabet 2 in string formed over w ϵ (0,1)* What u are talking about will be definately true if alphabet sent wouldn't contain 0 (in given question). We can't use one alphabet of alphabet set to define language over other set of alphabet,i.e. we can't use 0 of alphabet set to define language over a&b set of alphabet, 1 votes 1 votes Jason_Roy commented Feb 5, 2017 i edited by Jason_Roy Feb 5, 2017 reply Follow Share OK!! 0 votes 0 votes iita commented Feb 5, 2017 reply Follow Share yah got it @smriti012 thanks buddy 0 votes 0 votes Please log in or register to add a comment.