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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+13 votes

Which of the following is true for the language

$$\left\{ a^p \mid p \text{ is a prime } \right \}?$$

- It is not accepted by a Turing Machine
- It is regular but not context-free
- It is context-free but not regular
- It is neither regular nor context-free, but accepted by a Turing machine

+18 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.**

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 488
- Exam Queries 436
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,204 questions

43,662 answers

124,117 comments

42,948 users