38 38 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 14.0k views answer comment Share Follow Print See all 4 Comments 4 4 Comments reply mrinmoyh commented Sep 17, 2019 reply Follow flag 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). 10 10 replyShare Ajitgate21 commented Oct 17, 2022 reply Follow flag @mrinmoyh (TM is supposed to be the equivalent of modern computer) This line supper; but can you explain why not cfl? 0 0 replyShare Abhrajyoti00 commented Oct 18, 2022 reply Follow flag @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. 3 3 replyShare Gowtham_Kumar commented Jun 7 reply Follow flag We can write a algorithm to find the prime numbers hence it is DECIDABLE so it is recognized by a halting TM 0 0 replyShare Please log in or register to add a comment.
Best answer 50 50 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 5 5 Comments reply Show 2 previous comments akash.dinkar12 commented Sep 4, 2018 reply Follow flag mehul vaidya https://gateoverflow.in/104949/l-ap%C2%A0%E2%88%A3-p%C2%A0is-a-prime%C2%A0 1 1 replyShare mehul vaidya commented Sep 4, 2018 reply Follow flag @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 0 replyShare jaswanth431 commented Aug 9, 2021 reply Follow flag yes 0 0 replyShare Please log in or register to add a comment.
4 4 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 1 comment 1 1 comment reply anandhomkumare commented Jul 11, 2024 reply Follow flag CSL so it is must it is accepted by Turing machine. 2 2 replyShare Please log in or register to add a comment.
3 3 votes There is Theorem which says that language on single alphabet If regular then Context free also and If not regular then also not context free... mr.x answered Jan 10, 2025 mr.x comment Share Follow 0 reply Please log in or register to add a comment.
0 0 votes Ans is (D) Keith Kr answered Sep 12, 2014 Keith Kr comment Share Follow See all 5 Comments 5 5 Comments reply Show 2 previous comments rish1602 commented Nov 2, 2020 reply Follow flag why is it not Regular…. as in we can form NFA for it ?? 0 0 replyShare vaibhavkedia968 commented Nov 12, 2020 reply Follow flag 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 0 replyShare Sonu12345 commented Aug 24, 2022 reply Follow flag Try to make lba for given language? 0 0 replyShare Please log in or register to add a comment.
