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?

  • 1
    $\begingroup$ Do you doubt that it is context sensitive, or do you think it might be context free? $\endgroup$
    – rici
    Jul 13, 2021 at 17:24
  • $\begingroup$ If your question is about whether it's not a context-free language, use the pumping lemma. $\endgroup$
    – anomaly
    Jul 13, 2021 at 17:55
  • $\begingroup$ @rici, I thought that the context-sensitive proof considers that it is possible to check in finite time whether a number is prime, I haven't seen any linearly limited automaton of this type where you have the possibility of extending infinitely, so it sounded strange, so I think it don't be context sensitive. $\endgroup$
    – user206863
    Jul 13, 2021 at 19:03
  • $\begingroup$ @user: ok, i'll answer on that basis. $\endgroup$
    – rici
    Jul 13, 2021 at 19:49

1 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.


Not the answer you're looking for? Browse other questions tagged .