3

Let $L$ be a context-sensitive language, $s_{L}(n)$ is denoted by the number of words of length $n$ in $L$.

What is known about $s_{L}(n)$?

Note that it is known that $s_{L}(n)$ is either polynomial, or grows exponentially if $L$ is a context-free language.

Hermann Gruber
  • 6,470
  • 1
  • 35
  • 58
Blanco
  • 421
  • 2
  • 11
  • 2
    Possible duplicate of https://cstheory.stackexchange.com/questions/42190/size-of-complement-of-context-free-language. – domotorp Nov 23 '19 at 07:01
  • 1
    A simple note: for every (total) function $f(n)$ that can be computed by a LBA with unary input, you can make $s_L(n) = f(n)$ (just check $x < f(n)$) – Marzio De Biasi Nov 25 '19 at 07:47

0 Answers0