8,090 views
29 votes
29 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

3 Answers

Best answer
35 votes
35 votes

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
2 votes
2 votes

There ar some languages which except by LBA.( Must for Gate Aspirants)

See the 4th point which says the given language is CSL.

so it is neither Regular nor CFL, but it is CFL so it is must it is accepted by Turing machine. 

 

0 votes
0 votes
Ans is (D)
Answer:

Related questions

33 votes
33 votes
5 answers
2
48 votes
48 votes
3 answers
3