# Minimal Number of Symbols in Context-Free Grammar for a Special One-Letter Language

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.

• The smallest grammar for a string of length $n$ has size $\Omega(\log n)$ ( The Smallest Grammar Problem ). – Marzio De Biasi Jun 18 '12 at 16:18
• It seems to be that this paper only gives an approximation. I need a concrete minimal context-free grammar. – Ronny Jun 26 '12 at 10:15
• 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 Jun 26 '12 at 12:15