3 votes 3 votes L={ (an)m bn | n,m>=1 } Theory of Computation theory-of-computation + – VS asked Jan 20, 2018 VS 586 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply srivivek95 commented Jan 20, 2018 reply Follow Share Why not regular? L={axby,x,y>=1} 0 votes 0 votes joshi_nitish commented Jan 20, 2018 reply Follow Share no, it is not regular, neither it is CFL. 0 votes 0 votes srivivek95 commented Jan 20, 2018 reply Follow Share what is the language then? 0 votes 0 votes joshi_nitish commented Jan 20, 2018 reply Follow Share it is already given in qsn, see, if b has come 1000 times than a should come in a multiple of 1000, now there is strict dependency b/w a and b then how can it be regular 1 votes 1 votes Hemant Parihar commented Jan 20, 2018 reply Follow Share Yes, it is neither regular nor CFL. It is not CFL because we can check whether the #a is equal to #b, but #a can be any multiple of #b. It is CSL, as we can write C program to check whether the input is in this format or not. 1 votes 1 votes Hemant Parihar commented Jan 20, 2018 reply Follow Share If there is an upper limit on m then it is CFL. As L can be written as L = L1 U L2 U L3 U L4 U... finite times. L1 = { $a^n$$b^n$ | n >=1} L2 = { $a^{2n}$$b^n$ | n >=1} L3 = { $a^{3n}$$b^n$ | n >=1} L4 = { $a^{4n}$$b^n$ | n >=1} .... Finite times. We know that finite union of CFL is CFL. 1 votes 1 votes VS commented Jan 20, 2018 reply Follow Share @ Hemant Parihar It is CSL, as we can write C program to check whether the input is in this format or not. But, if we are able to write a program , it means that it is decidable and hence REC , how can we be sure that it is CSL? 0 votes 0 votes Hemant Parihar commented Jan 20, 2018 reply Follow Share @VS, Here we need to do the matching of a and b in some order. Which can be done using a TM whose tape size is linearly dependent on the input size. That's why CSL. 1 votes 1 votes Please log in or register to add a comment.