There is a trival algorithm checking primality using linear space (on a Turing machine). Thus there is a context-sensitive grammar for this language. However, there is no context-free grammar by a pumping argument.
The User
- 2.4k
- 23
- 24