Smallest grammar problem
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. 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. The problem is NP-complete.
The smallest context-free grammar that generates a given string is always a straight-line grammar without useless rules.
