The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+10 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
asked in Theory of Computation by Veteran (68.8k points) | 919 views

2 Answers

+16 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 = option D

answered by Veteran (30.5k points)
selected 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 ?
0 votes
Ans is (D)
answered by Boss (6.3k points)
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)

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

32,620 questions
39,267 answers
36,656 users