Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$

Question

I am looking for the minimal size of a context-free grammar which defines the finite language $$L_n=\{a^k\mid 1\le k\le n\}.$$ The size of a grammar is defined as the total length of all right-hand sides of the rules.
For example a grammar with $$S\to A_1A_1\\A_1\to A_2A_2\\A_2\to A_3A_3\\A_3\to A_4A_4\\A_4\to aa$$ has size $5\cdot 2=10$.
It is well-known that the minimal context-free grammar which defines the language only accepting the word $a^k$ has size $\Theta(\log k)$ (see the example above for the construction of the word $a^{32}$). Now, I am interested in the size of a grammar constructing all strings $a^k$ ($1\le k\le n$) for a given $n$. By the information above it is easy to create a grammar for $L_n$ of size $$\Theta(n+\sum_{k=1}^{n}\log k)=\Theta(\log n!)=\Theta(n\log n)$$ since we can create all words by a grammar of size $\Theta(\log k)$ and connect those grammars with a start rule of size $n$ (one symbol for each word). But since the final grammar is allowed to share nonterminals this construction is clearly not optimal. Maybe the smallest grammar has asymptotically the same size, but i don't know. Any help?

Answer 1

There is a grammar of size $O(\log n)$ using repeated squaring.

Let's start with the simpler case $n = 2^m$: $$ \begin{align*} &S \to a B_0 B_1 \dots B_{m-1} \\ &B_i \to A_i | \epsilon && (0 \leq i \leq m-1) \\ &A_i \to A_{i-1}A_{i-1} && (1 \leq i \leq m-1) \\ &A_0 \to a \end{align*} $$ Here $A_i \to a^{2^i}$ and $B_i \to a^{2^i}|\epsilon$.

More generally, suppose $n-1 = 2^{d_0} + 2^{d_1} + \cdots + 2^{d_\ell}$, where $d_0 > d_1 > \cdots > d_\ell$. The corresponding grammar is: $$ \begin{align*} &S \to a B_{d_0} | a C_0 B_{d_1} | a C_1 B_{d_2} | \cdots | a C_{\ell-1} B_{d_\ell} | aC_\ell \\ &C_j \to C_{j-1} A_{d_j} && (1 \leq j \leq \ell) \\ &C_0 \to A_{d_0} \\ &B_i \to B_{i-1} A_{i-1} | B_{i-1} && (1 \leq i \leq d_0) \\ &B_0 \to \epsilon \\ &A_i \to A_{i-1}A_{i-1} && (1 \leq i \leq d_0) \\ &A_0 \to a \end{align*} $$ Here $A_i \to a^{2^i}$, $B_i \to \{a^k : 0 \leq k < 2^i\}$ and $C_j \to a^{2^{d_0} + \cdots + 2^{d_j}}$.

As an extra property, both grammars are unambiguous.

Answer 2

This is a solution using repeated squaring, developed independently of that of Yuval Filmus. My purpose was to get as small a size as possible, not just low complexity. The resulting grammar is ambiguous, unlike that of Yuval Filmus.

The size obtained is bound by: $3\lfloor\log_2 (n-1)\rfloor+4$
This is about as low as one can get given that the squaring alone will require about $2\log_2 (n-1)+2$ size in optimal situations, when $n-1=2^p$

We define: $L_n=\{a^k\mid 1\leq k\leq n\}$
$H_n=\{a^k\mid 0\leq k\leq n\}$

Note that $L_n=aH_{n-1}$ and $H_n=L_n\cup\{\epsilon\}$

We can define recursively the rules

$A_p\to A_{p-1}A_{p-1}$

with a base case $A_0\to a \mid \epsilon $

Recall that a non-terminal can be read as the set of strings that derive from it. The advantage of squaring a set $A_k$ that contains $\epsilon$ is that $A_k$ is contained in the square $A_kA_k$ : $A_k\subseteq A_kA_k$

Taking the first $p+1$ such rules with $A_p$ as initial non-terminal symbol, we have a grammar that generates $H_{2^p}$ for any $p\geq 0} with a very small size.

That makes size $2$ (or is $\epsilon$ with size 0 ?) for the base rule and size $2$ for the other rules, thus $2(p+1)$ for the grammar size for $H_{2^p}$

We see that using $\epsilon$ is convenient, but it is not supposed to be in the final language, so we take one terminal $a$ aside, to be concatenated in the end.

Instead of considering $L_n$, we consider $H_{n-1}$, since $L_n=aH_{n-1}$

Now, to get a grammar for $H_{n-1}$ we consider the decomposition of $n-1$ into a sum of powers of two. For that one uses the binary representation of $m=n-1$ as:

$$m=n-1=\sum_{i=0}^{i=q}m_i2^i \text{ where } q=\lfloor\log_2 (n-1)\rfloor$$

Then you take in your grammar all the $q+1$ rules defining $A_i$ for $i\in[0,q]$, with a total size of $2(q+1)$

Then you add a last rule

$S\to A_{i_1}\ldots A_{i_k}\ldots A_{q}$ where the indices $i_k$ are all the indices such that $m_{i_k}=1$, the last one being of course $q$. The length of the right-hand side is at most $q+1$.

This addition of this last rule with $S$ as initial symbol defines a grammar for $H_{n-1}$.

To get a grammar for $L_n$, we must concatenate it to $a$, which can easily be achieved by adding $a$ to the right-hand side of the last rule which becomes:

$S\to aA_{i_1}\ldots A_{i_k}\ldots A_{q}$

This rule has a size which is $1$ more than the previous version, thus is upperbounded by $q+2$.

With the $q+1$ rules with total size $2(q+1)$ defining the $A_i$, we have a total of $q+2$ rules with a size upperbound of $3q+4$.

Taking $S$ as initial symbol, this grammar generates the language $L_n$, with $q=\lfloor\log_2 (n-1)\rfloor$.

Note: one thing here was inspired by Yuval Filmus: it was to use a single very long rule of size at most $q+2$ for the last one, rather than a CNF equivalent which nearly doubles the size to $2q+2$. Without this change the multiplicative constant would be $4$ instead of $3$.

Answer 3

I'm not sure if I understand correctly, but is there just a trivial $O(N)$ way to do this?

$A = a$

$S_0 = ""$ (I mean the empty rule, or $a^0$.)

$S_1 = S_0A$

$S_2 = S_1A$

$S_3 = S_2A$

$\cdots$

Please tell me if I misunderstood your problem (and feel free to ignore or delete my answer in that case).

Answer 4

There is a simple grammar of size $\Theta(n)$:

$\qquad\displaystyle\begin{align*} A_1 &\to a \\ A_i &\to aA_{i-1} \mid a, \quad 2 \leq i \leq n \end{align*}$

with starting symbol $A_n$. The right-hand sides sum up to $3(n-1) + 1 = 3n - 3$.