<p>This is essentially the problem of "addition chains", discussed in great detail in many papers and in Knuth's The Art of Computer Programming.  In brief:  the problem as you have stated it is not known to be NP-hard, but nobody knows an efficient algorithm to find the absolutely minimum.  However, there are good algorithms that come reasonably close to the minimum.</p>

CC BY-SA 3.0
2012-10-21T23:43:04.860Z
2012-10-21T23:43:04.860Z
Jeffrey Shallit
<p>Given is the language
$$L_n = \{a^n\},$$
where $n$ is a natural number and $a$ is a letter. <strong>What are the productions/rules of a minimal context-free grammar according to the number of symbols of the productions (e.g. the number of symbols of the productions $\{ S \rightarrow a, S \rightarrow aS \}$ is 7).</strong></p>

<p>For $n = 1$ the (only) rule is $\{ S \rightarrow a \}$ and for $n = 2$ we get $\{ S \rightarrow aa \}$, which can be proved easily. The number of symbols are $3$ and $4$, respectively. You may think, that $\{ S \rightarrow a^n \}$ ($2 + n$ Symbols) is always the shortest rule according the number of symbols for $L_n$ but $L_{10} = \{a^{10}\}$ can be constructed by $\{ S \rightarrow A^5, A \rightarrow aa \}$ that has only $11$ symbols (instead of $2 + 10 = 12$). This looks like an optimal compression problem.</p>

CC BY-SA 3.0
2012-06-18T16:18:15.773Z
The smallest grammar for a string of length $n$ has size $\Omega(\log n)$ ( [The Smallest Grammar Problem](http://www.cs.ucla.edu/~sahai/work/web/2005%20Publications/TransOnInfoTheory2005.pdf) ).
Marzio De Biasi
CC BY-SA 3.0
2012-06-26T10:15:00.847Z
It seems to be that this paper only gives an approximation. I need a concrete minimal context-free grammar.
Ronny
CC BY-SA 3.0
2012-06-26T12:15:48.607Z
from the article: "However, even if the $k_i$ are written in unary, apparently no polynomial time algorithm ...". So I think that if you need the minimal CF grammar you must start from the (good) approximation and enumerate+check all the shorter grammars.
Marzio De Biasi
<cc.complexity-theory><fl.formal-languages><context-free><context-free-languages>
Minimal Number of Symbols in Context-Free Grammar for a Special One-Letter Language
Ronny
# Minimal Number of Symbols in Context-Free Grammar for a Special One-Letter Language

(Asked by: username_0 on 2012-06-18)

Given is the language
$$L\_n = \{a^n\},$$
where $n$ is a natural number and $a$ is a letter. **What are the productions/rules of a minimal context-free grammar according to the number of symbols of the productions (e.g. the number of symbols of the productions $\{ S \rightarrow a, S \rightarrow aS \}$ is 7).**

For $n = 1$ the (only) rule is $\{ S \rightarrow a \}$ and for $n = 2$ we get $\{ S \rightarrow aa \}$, which can be proved easily. The number of symbols are $3$ and $4$, respectively. You may think, that $\{ S \rightarrow a^n \}$ ($2 + n$ Symbols) is always the shortest rule according the number of symbols for $L\_n$ but $L\_{10} = \{a^{10}\}$ can be constructed by $\{ S \rightarrow A^5, A \rightarrow aa \}$ that has only $11$ symbols (instead of $2 + 10 = 12$). This looks like an optimal compression problem.

**Tags:** cc.complexity-theory, fl.formal-languages, context-free, context-free-languages

> **Comments:**
> **username_1**: The smallest grammar for a string of length $n$ has size $\Omega(\log n)$ ( [The Smallest Grammar Problem](http://www.cs.ucla.edu/~sahai/work/web/2005%20Publications/TransOnInfoTheory2005.pdf) ).  
> **username_0**: It seems to be that this paper only gives an approximation. I need a concrete minimal context-free grammar.  
> **username_1**: from the article: "However, even if the $k_i$ are written in unary, apparently no polynomial time algorithm ...". So I think that if you need the minimal CF grammar you must start from the (good) approximation and enumerate+check all the shorter grammars.  

---

## 1 answers

### Answer by username_2 on 2012-10-21. Score: 10

This is essentially the problem of "addition chains", discussed in great detail in many papers and in Knuth's The Art of Computer Programming. In brief: the problem as you have stated it is not known to be NP-hard, but nobody knows an efficient algorithm to find the absolutely minimum. However, there are good algorithms that come reasonably close to the minimum.


---

