<p>Let <span class="math-container">$L$</span> be a context-sensitive language, <span class="math-container">$s_{L}(n)$</span> is denoted by the number of words of length <span class="math-container">$n$</span> in <span class="math-container">$L$</span>.</p>

<p>What is known about <span class="math-container">$s_{L}(n)$</span>?</p>

<p>Note that <a href="https://cstheory.stackexchange.com/questions/41878/number-of-words-of-length-n-in-a-context-free-language?rq=1">it is known</a> that <span class="math-container">$s_{L}(n)$</span> is either polynomial, or grows exponentially if <span class="math-container">$L$</span> is a context-free language.</p>

CC BY-SA 4.0
2019-11-23T07:01:58.953Z
Possible duplicate of https://cstheory.stackexchange.com/questions/42190/size-of-complement-of-context-free-language.
domotorp
CC BY-SA 4.0
2019-11-25T07:47:56.543Z
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
<fl.formal-languages><space-bounded>
The number of words of length $n$ in a context-sensitive language
Blanco
# The number of words of length $n$ in a context-sensitive language

(Asked by: username_0 on 2019-11-23)

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](https://cstheory.stackexchange.com/questions/41878/number-of-words-of-length-n-in-a-context-free-language?rq=1) that $s\_{L}(n)$ is either polynomial, or grows exponentially if $L$ is a context-free language.

**Tags:** fl.formal-languages, space-bounded
> **Comments:**
> **username_1**: Possible duplicate of https://cstheory.stackexchange.com/questions/42190/size-of-complement-of-context-free-language.  
> **username_2**: 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)$)  

---

## 0 answers

