Indata compression and the theory offormal languages, thesmallest grammar problem is the problem of finding the smallestcontext-free grammar that generates a givenstring 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.^[1]Others also add the number of rules to that.^[2] A grammar that generates only a single string, as required for the solution to this problem, is called astraight-line grammar.^[3]

Everybinary string of length${\displaystyle n}$ has a grammar of length${\displaystyle O(n/\log n)}$, as expressed usingbig O notation.^[3] For binaryde Bruijn sequences, no better length is possible.^[4]

The (decision version of the) smallest grammar problem isNP-complete.^[1]It can be approximated inpolynomial time to within a logarithmicapproximation ratio; more precisely, the ratio is${\displaystyle O(\log \frac{n}{g})}$ where${\displaystyle n}$ is the length of the given string and${\displaystyle g}$ is the size of its smallest grammar. It is hard to approximate to within a constant approximation ratio. An improvement of the approximation ratio to${\displaystyle o(\log n/\log \log n)}$ would also improve certain algorithms for approximateaddition chains.^[5]

• Grammar-based code
• Kolmogorov complexity
• Lossless data compression

• "CFG-Kolm-complexity is singleton sets with Lance and Bill".Computational Complexity. June 9, 2024.

Thisalgorithms ordata structures-related article is astub. You can help Wikipedia byadding missing information.

• v
• t
• e

• Formal languages
• Data compression
• NP-complete problems
• Algorithms and data structures stubs

• All stub articles