1 votes 1 votes The language of primes in unary is: A. Regular B. CFL C. DCFL D. Context Sensitive Theory of Computation theory-of-computation + – Deepak Sharma 1 asked Aug 16, 2015 Deepak Sharma 1 2.9k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
8 votes 8 votes D.Context sensitive it will be l={1^p where p is prime} ..it cant be regular as there is no pattern in the strings generated that we can remember, also we cant generate primes using FA+ one stack ie pda. Anurag_s answered Aug 16, 2015 Anurag_s comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Himanshu1 commented Oct 30, 2015 reply Follow Share How to know that Tape length would be linear?? 0 votes 0 votes Anurag_s commented Oct 30, 2015 reply Follow Share That is by definition of lba 0 votes 0 votes Himanshu1 commented Oct 30, 2015 reply Follow Share no no , I m asking how we know that primes can be done with Linear tape Turing Machine ?? 0 votes 0 votes Please log in or register to add a comment.