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.[1]
Others also add the number of rules to that.[2] The (decision version of the) problem is
NP-complete.[1]
The smallest context-free grammar that generates a given string is always a
straight-line grammar without
useless rules.[citation needed]
^Florian Benz and Timo Kötzing, “An effective heuristic for the smallest grammar problem,” Proceedings of the fifteenth annual conference on Genetic and evolutionary computation conference - GECCO ’13, 2013.
ISBN978-1-4503-1963-8doi:
10.1145/2463372.2463441