1.5k 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
+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 ?
0
so what is type of language ?

is it recursive .
0
0
@akash.dinkar

there is one statement in link you provided

"NDTM halts on every input and language accepted by NDTM will be CSL "

Do you know any reference for this?

I tried to search on net , i did not find anything useful
Ans is (D)
0
please explain how come TM accepts it?
+2
Because It is a CSL and it can be easily accepted by Linear Bound Aoutomata, hence accepted by Turing Machine. therfore D)

1
2