In data compression and the theory of formal languages, the smallest grammar problem is the problem of finding the smallest context-free grammar that generates a given string of characters (but no other string).
The size of a grammar is defined by some authors as the number of symbols on the right side of the production rules.
[2] A grammar that generates only a single string, as required for the solution to this problem, is called a straight-line grammar.
[3] For binary de Bruijn sequences, no better length is possible.
[4] The (decision version of the) smallest grammar problem is NP-complete.
would also improve certain algorithms for approximate addition chains.
This algorithms or data structures-related article is a stub.