Example of an context-sensitive language with a specific number of words of length $n$

Question

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$.

Answer 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$.)