3 3 votes L={ (an)m bn | n,m>=1 } Theory of Computation theory-of-computation + – VS 1.4k views answer comment Share Follow Print See all 8 Comments 8 8 Comments reply srivivek95 commented Jan 20, 2018 reply Follow flag Why not regular? L={axby,x,y>=1} 0 0 replyShare joshi_nitish commented Jan 20, 2018 reply Follow flag no, it is not regular, neither it is CFL. 0 0 replyShare srivivek95 commented Jan 20, 2018 reply Follow flag what is the language then? 0 0 replyShare joshi_nitish commented Jan 20, 2018 reply Follow flag 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 1 replyShare Hemant Parihar commented Jan 20, 2018 reply Follow flag 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 1 replyShare Hemant Parihar commented Jan 20, 2018 reply Follow flag 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 1 replyShare VS commented Jan 20, 2018 reply Follow flag @ 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 0 replyShare Hemant Parihar commented Jan 20, 2018 reply Follow flag @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 1 replyShare Please log in or register to add a comment.
