GATE 2001
November 17, 2024GATE-2024-CS1(Forenoon)
November 17, 2024GATE 2008
| Question 9 |
Which of the following is true for the language {ap|p is a prime} ?
| 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 |
Question 9 Explanation:
Finding prime number cannot be done by FA or PDA, so it cannot be regular or CFL. This language can be recognized by LBA, hence it can be accepted by Turing Machine.
Correct Answer: D
Question 9 Explanation:
Finding prime number cannot be done by FA or PDA, so it cannot be regular or CFL. This language can be recognized by LBA, hence it can be accepted by Turing Machine.