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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Do you doubt that it is context sensitive, or do you think it might be context free? $\endgroup$– riciJul 13, 2021 at 17:24
-
$\begingroup$ If your question is about whether it's not a context-free language, use the pumping lemma. $\endgroup$– anomalyJul 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$– user206863Jul 13, 2021 at 19:03
-
$\begingroup$ @user: ok, i'll answer on that basis. $\endgroup$– riciJul 13, 2021 at 19:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
