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

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?

• Adding $A_4\to a$ and $A_4\to \lambda$ would help a lot in your case, and seems to be applicable in general. – Hendrik Jan Jul 24 '15 at 11:36
• Do you consider the empty rule $U\to\lambda$ as having size $0$ or size $1$. --- Is there a specific reason for this choice of grammar size definition, or was it just arbitrary? You could have considered also a cost of 1 for each rule. --- Besides, I am curious as to the applications or context for this problem. Do you have any? – babou Jul 26 '15 at 13:27
• @babou The empty rule hase size 0 in this definiton. Yes there is an application. There are so called straight line programs (SLPs) to compress words with context free grammars. The the size of a grammar as defined in my question is the usual way in various papers to define the grammar size in this context. If we consider some kind of normal form like CNF it is also possible to count the rules since it is nearly the same. My question comes from this context, because in my opinion it is senseful to think about grammars as a compressor for languages instead of single words, too. – Danny Jul 26 '15 at 13:53
• Thanks. So given your application, I guess absolute optimality is as important as asymptotic growth optimality? Or is it? This might just be an example for complexity assessment? Your title says "minimal size", not "minimal asymptotic size growth" --- But is your existing application for single word languages, or is it also for languages like $L_n$ ? --- And I suppose you use strings that are more structured than $a^k$. – babou Jul 26 '15 at 14:13
• My interests are mostly about asymptotics, but you are right, the exact size is also very interesting, so thanks again for your answer. The original purpose of SLPs is about compressing a single word. But there is related work in the recent literature about compressing finite languages, too. – Danny Jul 26 '15 at 14:57

4 Answers

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.

• I can read of that the grammar is of size $\Theta(d_0 + \ell) = \Theta(d_0)$ (since $\ell \leq d_0$). The only immediate bound on $n$ I see is $n \leq \ell \cdot 2^{d_0} + 1$; from there, I don't get to the logarithmic size bound. What am I missing? – Raphael Jul 24 '15 at 13:57
• @Raphael You are missing that $2^{d_0} + \cdots + 2^{d_\ell}$ is the binary expansion of $n-1$. – Yuval Filmus Jul 24 '15 at 13:58
• Ah, right: $n \leq 2^{d_0 + 1}$. Thanks. – Raphael Jul 24 '15 at 14:01
• It seems that you have the answer to most of my questions, thanks again. – Danny Jul 24 '15 at 16:48

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$. I'm not sure if I understand correctly, but is there just a trivial$O(N)$way to do this?$A = aS_0 = ""$(I mean the empty rule, or$a^0$.)$S_1 = S_0AS_2 = S_1AS_3 = S_2A\cdots$Please tell me if I misunderstood your problem (and feel free to ignore or delete my answer in that case). • This grammar generates$a^n$rather than$\{a^1,\ldots,a^n\}$. – Yuval Filmus Jul 24 '15 at 14:09 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\$.

• This can be exponentially improved. – Yuval Filmus Jul 24 '15 at 14:08