ISRO-DEC2017-25

Question

Let $L=\{a^p\mid p \text{ is a  prime}\}.$ Then which of the following is true

• 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

Answer 1

The language is an example of Context Sensitive Language which is not context free, therefore, it will be accepted by a Turing Machine. Option D is the correct answer.