Let L = {ap | p is a prime}. Then which of the following is true? , ISRO 2017
2017
Let L = {ap | p is a prime}. Then which of the following is true? , ISRO 2017
- A.
It is not accepted by a Turing Machine
- B.
It is regular but not context free
- C.
It is context free but not regular
- D.
It is neither regular nor context free, but accepted by a Turing Machine
Attempted by 41 students.
Show answer & explanation
Correct answer: D
The language L = {a^p | p is prime} consists of strings with prime lengths. 1) Not Regular: By the Pumping Lemma, regular languages require periodic length patterns, but prime numbers are not periodic. 2) Not Context-Free: Parikh's Theorem implies CFL lengths must be semilinear, which primes are not. 3) Turing-Recognizable: Primality testing is decidable; a Turing Machine can verify if the input length is prime. Thus, L is neither regular nor context-free but is Turing-recognizable.