The GATE Grind

GATE 2008 CS – Question 9

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 1 mark · Multiple choice

Which statement is true of $\{a^p\mid p\text{ is prime}\}$?

  1. Not accepted by a Turing machine.
  2. Regular but not context-free.
  3. Context-free but not regular.
  4. Neither regular nor context-free, but accepted by a Turing machine.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) Neither regular nor context-free, but accepted by a Turing machine.

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Regular and Context-Free Languages, Pumping Lemma questions

All Regular and Context-Free Languages, Pumping Lemma questions →