Example of an context-sensitive language with a specific number of words of length $n$ Let $s_L(n)$ denote the number of words of length $n$ in $L$.
For context-free languages it is known that $s_L(n)$ is either polynomial or exponential.
For context-sensitive languages this is probably not true and I would like to study counterexamples.
I am interested in an example of a context-sensitive language that has $s_L(n)=\Theta(r^{(n^\delta)})$ for a real $r&gt;1$ and $\delta&lt;1$ or $s_L(n)=\Theta(r^{(log^c(n))})$ for $c&gt;1$.
The language
$$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor n^\delta\rfloor}0^{n-\lfloor n^\delta\rfloor}$$
is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\lfloor n^\delta\rfloor}$.
The language
$$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor(\log n)^c\rfloor}0^{n-\lfloor(\log n)^c\rfloor}$$
is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\lfloor(\log n)^c\rfloor}$.
You can construct any number of examples like this. Basically, if $f\colon\mathbb N\to\mathbb N$ is any function such that given $n$ in binary, $f(n)$ (in binary) is computable in space $O(n)$ (which is exponential space in terms of the length of its input) and $f(n)\le2^n$, then there exist languages $L\in\mathrm{DSPACE}(n)\subseteq\mathrm{CSL}$ such that $s_L(n)=f(n)$, such as
$$L=\bigcup_{n\in\mathbb N}\bigl\{w\in\{0,1\}^n:w&lt;_\mathrm{Lex}\operatorname{bin}(f(n))\bigr\},$$
where $&lt;_\mathrm{Lex}$ denotes lexicographic order, and $\operatorname{bin}(f(n))\in\{0,1\}^n$ is the binary expansion of $f(n)$.