# 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>1$$ and $$\delta<1$$ or $$s_L(n)=\Theta(r^{(\log^c(n))})$$ for $$c>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<_\mathrm{Lex}\operatorname{bin}(f(n))\bigr\},$$ where $$<_\mathrm{Lex}$$ denotes lexicographic order, and $$\operatorname{bin}(f(n))\in\{0,1\}^n$$ is the binary expansion of $$f(n)$$.

In fact, it is easy to give an exact characterization along the same lines. Let me say that a nondeterministic TM computes a function $$f\colon \mathbb N\to\mathbb N$$ if for every input $$x\in\mathbb N$$ (in binary),

• there exists a run of the machine that computes $$f(x)$$ (in binary), and

• all runs either compute $$f(x)$$ or report a failure.

Then using the construction above and the Immerman–Szelepcsényi theorem, one can show that for any $$f\colon\mathbb N\to\mathbb N$$, the following are equivalent:

• $$f=s_L$$ for some language $$L\in\mathrm{CSL}$$;

• $$f(n)$$ is computable on a nondeterministic TM in space $$O(n)$$, including the size of the output.

(Note that base conversion can be done in linear space, hence it is immaterial whether we choose binary or any other base $$b\ge2$$.)