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

+14 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

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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,932 questions

52,335 answers

182,384 comments

67,817 users