Project ForgeTheory of Computation
Grammars, Turing Machines & Decidability
GATE 2008
Hard
Which of the following is true for the language {aᵖ | p is a prime}?
- AIt is not accepted by a Turing Machine
- BIt is regular but not context-free
- CIt is context-free but not regular
- It is neither regular nor context-free, but accepted by a Turing machine
Explanation
{aᵖ | p prime} is not regular (classic pumping-lemma result) and not context-free either (also provable via the CFL pumping lemma). But primality is decidable, so a Turing machine can simulate a primality test on the input length and accept accordingly — it's recursive, hence certainly Turing-machine-acceptable.
Source: GATE CS 2008 (2008)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.