3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Possible duplicate of cstheory.stackexchange.com/questions/42190/…. $\endgroup$
    – domotorp
    Nov 23, 2019 at 7:01
  • 1
    $\begingroup$ 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)$) $\endgroup$
    – Marzio De Biasi
    Nov 25, 2019 at 7:47

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.