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

+20 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.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.6k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.3k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 480
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,748 questions

47,471 answers

145,586 comments

62,234 users