<p>The language
<span class="math-container">$$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor n^\delta\rfloor}0^{n-\lfloor n^\delta\rfloor}$$</span>
is computable in <span class="math-container">$\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$</span>, and it has <span class="math-container">$s_L(n)=2^{\lfloor n^\delta\rfloor}$</span>.</p>
<p>The language
<span class="math-container">$$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor(\log n)^c\rfloor}0^{n-\lfloor(\log n)^c\rfloor}$$</span>
is computable in <span class="math-container">$\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$</span>, and it has <span class="math-container">$s_L(n)=2^{\lfloor(\log n)^c\rfloor}$</span>.</p>
<p>You can construct any number of examples like this. Basically, if <span class="math-container">$f\colon\mathbb N\to\mathbb N$</span> is any function such that given <span class="math-container">$n$</span> in binary, <span class="math-container">$f(n)$</span> (in binary) is computable in space <span class="math-container">$O(n)$</span> (which is <em>exponential</em> space in terms of the length of its input) and <span class="math-container">$f(n)\le2^n$</span>, then there exist languages <span class="math-container">$L\in\mathrm{DSPACE}(n)\subseteq\mathrm{CSL}$</span> such that <span class="math-container">$s_L(n)=f(n)$</span>, such as
<span class="math-container">$$L=\bigcup_{n\in\mathbb N}\bigl\{w\in\{0,1\}^n:w&lt;_\mathrm{Lex}\operatorname{bin}(f(n))\bigr\},$$</span>
where <span class="math-container">$&lt;_\mathrm{Lex}$</span> denotes lexicographic order, and <span class="math-container">$\operatorname{bin}(f(n))\in\{0,1\}^n$</span> is the binary expansion of <span class="math-container">$f(n)$</span>.</p>
<p>In fact, it is easy to give an exact characterization along the same lines. Let me say that a nondeterministic TM computes a function <span class="math-container">$f\colon \mathbb N\to\mathbb N$</span> if for every input <span class="math-container">$x\in\mathbb N$</span> (in binary),</p>
<ul>
<li><p>there exists a run of the machine that computes <span class="math-container">$f(x)$</span> (in binary), and</p>
</li>
<li><p>all runs either compute <span class="math-container">$f(x)$</span> or report a failure.</p>
</li>
</ul>
<p>Then using the construction above and the Immerman–Szelepcsényi theorem, one can show that for any <span class="math-container">$f\colon\mathbb N\to\mathbb N$</span>, the following are equivalent:</p>
<ul>
<li><p><span class="math-container">$f=s_L$</span> for some language <span class="math-container">$L\in\mathrm{CSL}$</span>;</p>
</li>
<li><p><span class="math-container">$f(n)$</span> is computable on a nondeterministic TM in space <span class="math-container">$O(n)$</span>, including the size of the output.</p>
</li>
</ul>
<p>(Note that base conversion can be done in linear space, hence it is immaterial whether we choose binary or any other base <span class="math-container">$b\ge2$</span>.)</p>

CC BY-SA 4.0
2021-05-29T08:16:24.703Z
2021-05-31T10:57:30.140Z
2021-05-31T10:57:30.140Z
Emil Jeřábek
<p>Let <span class="math-container">$s_L(n)$</span> denote the number of words of length <span class="math-container">$n$</span> in <span class="math-container">$L$</span>.</p>
<p>For context-free languages it is known that <span class="math-container">$s_L(n)$</span> is either polynomial or exponential.
For context-sensitive languages this is probably not true and I would like to study counterexamples.</p>
<p>I am interested in an example of a context-sensitive language that has <span class="math-container">$s_L(n)=\Theta(r^{(n^\delta)})$</span> for a real <span class="math-container">$r&gt;1$</span> and <span class="math-container">$\delta&lt;1$</span> or <span class="math-container">$s_L(n)=\Theta(r^{(\log^c(n))})$</span> for <span class="math-container">$c&gt;1$</span>.</p>

<fl.formal-languages><space-bounded>
Example of an context-sensitive language with a specific number of words of length $n$
Ignirion
# Example of an context-sensitive language with a specific number of words of length $n$

(Asked by: username_0 on 2021-05-28)

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

**Tags:** fl.formal-languages, space-bounded

---

## 1 answers

### Answer by username_1 on 2021-05-29. Score: 11 | Accepted answer

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


---

