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

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?

• Do you doubt that it is context sensitive, or do you think it might be context free?
– rici
Jul 13, 2021 at 17:24
• If your question is about whether it's not a context-free language, use the pumping lemma. Jul 13, 2021 at 17:55
• @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. Jul 13, 2021 at 19:03
• @user: ok, i'll answer on that basis.
– rici
Jul 13, 2021 at 19:49

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.