Which of the following is true for the language
2008
Which of the following is true for the language 
- 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 7 students.
Show answer & explanation
Correct answer: D
The language {ap | p is a prime} consists of strings of 'a' characters where the length is a prime number. This language is not regular because the set of prime numbers does not follow a periodic pattern, which violates the pumping lemma for regular languages. It is also not context-free because the distribution of primes cannot be captured by a pushdown automaton. However, since prime numbers are recursively enumerable (there exists an algorithm to list all primes), the language is recursively enumerable and thus accepted by a Turing machine.
A video solution is available for this question — log in and enroll to watch it.