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. Others also add the number of rules to that. A grammar that generates only a single string, as required for the solution to this problem, is called a straight-line grammar.

Every binary string of length n {\displaystyle n} has a grammar of length O ( n / log ⁡ n ) {\displaystyle O(n/\log n)}, as expressed using big O notation. For binary de Bruijn sequences, no better length is possible.

The (decision version of the) smallest grammar problem is NP-complete. It can be approximated in polynomial time to within a logarithmic approximation ratio; more precisely, the ratio is O ( log ⁡ n g ) {\displaystyle O(\log {\tfrac {n}{g}})} where n {\displaystyle n} is the length of the given string and g {\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 o ( log ⁡ n / log ⁡ log ⁡ n ) {\displaystyle o(\log n/\log \log n)} would also improve certain algorithms for approximate addition chains.

See also

External links

  • . Computational Complexity. June 9, 2024.