29 votes 29 votes Which of the following is true for the language $$\left\{ a^p \mid p \text{ is a prime } \right \}?$$ It is not accepted by a Turing Machine It is regular but not context-free It is context-free but not regular It is neither regular nor context-free, but accepted by a Turing machine Theory of Computation gatecse-2008 theory-of-computation easy identify-class-language + – Kathleen asked Sep 11, 2014 Kathleen 8.3k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply mrinmoyh commented Sep 17, 2019 reply Follow Share TM is supposed to be the equivalent of modern computer. Now in modern computer we can write program to find prime numbers.i.e there is an algorithm to do this. so,this is accepted by TM, moreover it's a Recursive language(halting TM). 4 votes 4 votes Ajitgate21 commented Oct 17, 2022 reply Follow Share @mrinmoyh (TM is supposed to be the equivalent of modern computer) This line supper; but can you explain why not cfl? 0 votes 0 votes Abhrajyoti00 commented Oct 18, 2022 reply Follow Share @Ajitgate21 To prove $a^p$ is prime we need division operation on infinite powers which is not possible by PDA. This is why it is not CFL. 0 votes 0 votes Please log in or register to add a comment.
Best answer 35 votes 35 votes We have algorithms to generate prime numbers $\implies$ we can generate sequence of $p$ for the given language, hence strings as defined by the language definition. So, by Church Turing Thesis we can say that there exists a Turing Machine which can accept the given language. Answer is option D. amarVashishth answered Nov 8, 2015 • edited Jun 15, 2018 by Milicevic3306 amarVashishth comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments akash.dinkar12 commented Sep 4, 2018 reply Follow Share mehul vaidya https://gateoverflow.in/104949/l-ap%C2%A0%E2%88%A3-p%C2%A0is-a-prime%C2%A0 0 votes 0 votes mehul vaidya commented Sep 4, 2018 reply Follow Share @akash.dinkar there is one statement in link you provided "NDTM halts on every input and language accepted by NDTM will be CSL " Do you know any reference for this? I tried to search on net , i did not find anything useful 0 votes 0 votes jaswanth431 commented Aug 9, 2021 reply Follow Share yes 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes There ar some languages which except by LBA.( Must for Gate Aspirants) See the 4th point which says the given language is CSL. so it is neither Regular nor CFL, but it is CFL so it is must it is accepted by Turing machine. Surya_Dev Chaturvedi answered Jan 15, 2021 Surya_Dev Chaturvedi comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Ans is (D) Keith Kr answered Sep 12, 2014 Keith Kr comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments rish1602 commented Nov 2, 2020 reply Follow Share why is it not Regular…. as in we can form NFA for it ?? 0 votes 0 votes vaibhavkedia968 commented Nov 12, 2020 reply Follow Share The language given in the question is a well known example of CSL, and it can be proved that it is not RL or CFL using their respective pumping lemmas. 0 votes 0 votes Sonu12345 commented Aug 24, 2022 reply Follow Share Try to make lba for given language? 0 votes 0 votes Please log in or register to add a comment.