Is $L = \{ a^p : \text{$p$ is prime} \}$ a context-sensitive language?

Question

I found a definition on Wikipedia that states that the language $L = \{ a^p : \text{$p$ is prime} \}$ is a context-sensitive language. Can someone explain or refute?

Answer 1

One simple solution is to use something like the Sieve of Erastothenes.

You start with two a $0$ followed by n-1 $a$s followed by an end-marker. Then you repeatedly find the first $a$ in the input. If that $a$ is at the end of the input, then change all the preceding $0$s to $a$; that's an acceptable input. If you don't find an $a$ before the end of the input, then $n$ is not a prime. Otherwise, change the $a$ and the symbol at every multiple of its position to 0 and repeat.

Actually writing out a context-sensitive grammar which does this is tedious, but I hope that sketch shows that it is possible.