+14 votes
1.7k 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
asked | 1.7k views

## 2 Answers

+21 votes
Best answer

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.

Answer is option D.

answered by Boss (30.9k points)
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
@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
0 votes
Ans is (D)
answered by Loyal (6.1k points)
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)
Answer:

+17 votes
4 answers
2
+25 votes
3 answers
3
+13 votes
2 answers
5
+38 votes
3 answers
7