2 votes 2 votes L={ (anbn)* | n>0 } Theory of Computation theory-of-computation identify-class-language + – VS asked Dec 28, 2017 VS 599 views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Anu007 commented Dec 28, 2017 i edited by Anu007 Dec 28, 2017 reply Follow Share No CFL. 0 votes 0 votes joshi_nitish commented Dec 28, 2017 reply Follow Share it is not even CFL, L is CSL it is not actually L* where L={anbn |n>0} language will look like L = {(ab)* + (aabb)* + (aaabbb)* + (aaaabbbb)*.............} and see carefully actually L is not even CFL, L is CSL. 3 votes 3 votes srestha commented Dec 28, 2017 reply Follow Share yes it can take (aaaabbbbaaaabbbb) =anbnanbn 2 votes 2 votes SHUBHAM SHASTRI commented Dec 28, 2017 reply Follow Share thanks a lot for correction.. 0 votes 0 votes Anu007 commented Dec 28, 2017 reply Follow Share :p...... 0 votes 0 votes srestha commented Dec 28, 2017 reply Follow Share :p @VS it is not CFL and not regular for sure 0 votes 0 votes srestha commented Dec 28, 2017 reply Follow Share But is it CSL Can it be done in 2 stacks? 0 votes 0 votes joshi_nitish commented Dec 28, 2017 reply Follow Share @VS analyze a given language by me, it is expansion of a language that you have asked. now see, above language contain a10b10a10b10 but does not contain a10b10a9b9 it would be CFL if qsn would be L=({anbn |n>0})* 0 votes 0 votes VS commented Dec 28, 2017 reply Follow Share @joshi_nitish You are absolutely correct ! Type 1 : L={ (anbn)* | n>0 } --> CSL Why ? eg: a10b10a10b10 ; 1 comparison to ensure 1st occurrence of a's=1st occurrence of b's 1 comparison to ensure 1st occurrence of b's=2nd occurrence of a's Min 2 comparisons --> CSL Type 2 : L={ (anbn) | n>0 }* --> DCFL Why ? eg: a10b10a9b9 ; 1 comparison to ensure 1st occurrence of a's=1st occurrence of b's Here, no need to ensure 1st occurrence of b's=2nd occurrence of a's Min 1 comparisons --> CFL 1 votes 1 votes joshi_nitish commented Dec 28, 2017 i edited by joshi_nitish Dec 28, 2017 reply Follow Share @VS yes, now you are exactly correct, infact CFL are closed under kleen closer, and {anbn |n>=1} is CFL, but more precisely ({anbn |n>=1})* is DCFL. 2 votes 2 votes Pawan Kumar 2 commented Dec 28, 2017 reply Follow Share joshi_nitish Sir , can you explain a little about how a10b10a9b9 belongs to ({anbn |n>=1})* .. thank u 0 votes 0 votes Anu007 commented Dec 28, 2017 reply Follow Share L = {......, a9b9, a10b10.....} L*= contain a9b9a10b10 and a10b10a9b9 1 votes 1 votes Pawan Kumar 2 commented Dec 28, 2017 reply Follow Share got it .... Thank u Anu007 Sir 0 votes 0 votes Please log in or register to add a comment.