GATE CSE 2008 | Question: 9

Question

Which of the following is true for the language

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

• A. It is not accepted by a Turing Machine
• B. It is regular but not context-free
• C. It is context-free but not regular
• D. It is neither regular nor context-free, but accepted by a Turing machine

Comments

TM is supposed to be the equivalent of modern computer.

Now in modern computer we can write program to find prime numbers.i.e there is an algorithm to do this.

so,this is accepted by TM, moreover it's a Recursive language(halting TM).

---

@mrinmoyh (TM is supposed to be the equivalent of modern computer) This line supper;  but can you explain why not cfl?

---

@Ajitgate21 To prove $a^p$ is prime we need division operation on infinite powers which is not possible by PDA. This is why it is not CFL.

Answer 1

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.

Comments

mehul vaidya 

https://gateoverflow.in/104949/l-ap%C2%A0%E2%88%A3-p%C2%A0is-a-prime%C2%A0

---

@akash.dinkar

there is one statement in link you provided

"NDTM halts on every input and language accepted by NDTM will be CSL "

Do you know any reference for this?

I tried to search on net , i did not find anything useful

---

yes

Answer 2

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

See the 4^th 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. 

 

Answer 3

Ans is (D)

Comments

why is it not Regular…. as in we can form NFA for it ??

---

The language given in the question is a well known example of CSL, and it can be proved that it is not RL or CFL using their respective pumping lemmas.

---

Try to make lba for given language?