The Gateway to Computer Science Excellence
+18 votes

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
in Theory of Computation by | 2.5k views
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).

2 Answers

+25 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.

edited by
It is CSL so it will be accepted by LBA hence it can also be accepted by Turing Machine. Is this approach is correct ?
so what is type of language ?

is it recursive .

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)
please explain how come TM accepts it?
Because It is a CSL and it can be easily accepted by Linear Bound Aoutomata, hence accepted by Turing Machine. therfore D)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,497 answers
95,320 users