1.1k views

Which of the following is true for the language

$$\left\{ a^p \mid p \text{ is a prime } \right \}?$$

1. It is not accepted by a Turing Machine
2. It is regular but not context-free
3. It is context-free but not regular
4. It is neither regular nor context-free, but accepted by a Turing machine

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.

edited by
+3
It is CSL so it will be accepted by LBA hence it can also be accepted by Turing Machine. Is this approach is correct ?
Ans is (D)
0
please explain how come TM accepts it?
+1
Because It is a CSL and it can be easily accepted by Linear Bound Aoutomata, hence accepted by Turing Machine. therfore D)