2.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
| 2.5k views
0
TM is supposed to be the equivalent of modern computer.

Now in modern computer we can write program to find prime numbers.i.e there is an algorithm to do this.

so,this is accepted by TM, moreover it's a Recursive language(halting TM).

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
+4
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
@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