5
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.