Skip to main content
2 of 2
typo
The User
  • 2.4k
  • 23
  • 24

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