Does the grammar generate many possible strings?

Not in this problem. It must generate exactly the specified string.

Is a smaller grammar always a smaller file?

No. The mathematical symbol count and the bits needed to encode rules and identifiers are different measurements.

Can a heuristic still be useful without finding the optimum?

Yes. A compact, correct result may be valuable. Describe its measured performance and any proven guarantee without promoting it to an exact solution.

AI Glossary / MLOps and deployment / Advanced

Smallest grammar problem

Definition

The smallest grammar problem asks for the most compact context-free grammar that generates exactly one specified string. In the standard size measure used here, compactness means the total number of symbols on the right-hand sides of all production rules, including the starting rule.

What it means

Imagine a long sequence containing repeated pieces. Instead of storing every occurrence, we can name a piece once and reuse its name. Larger pieces can themselves be built from smaller named pieces, creating a hierarchy that expands back into the original sequence.

Finding some useful hierarchy is different from proving that no smaller one exists. That global optimization question is the smallest grammar problem. “Grammar” refers to formal rewriting rules, not necessarily the rules of a spoken language. The goal is to reproduce this particular string, not to generate an unlimited collection of plausible sentences.

How it works

Start with a sequence of terminal symbols, such as characters or event labels. Introduce nonterminal symbols as reusable names for sequences. A starting symbol identifies the complete output. Expanding the definitions must recover exactly the input, with no alternatives producing additional strings.

Candidate grammars trade definition costs against reuse. Naming a short piece that occurs only once can increase the total size; a repeated piece may justify its definition. Choices interact because one named piece can become part of another.

The general optimization problem is computationally difficult: its decision version is NP-complete. Practical approaches therefore often seek good small grammars or approximation guarantees rather than exact optimality on arbitrary large inputs. A compression algorithm's useful output is not by itself a certificate that the mathematical optimum has been reached.

Three practical examples

1. Repeated event streams: an analyst can represent recurring event sequences with shared rules. The result offers a compact structural view, although a repeated sequence does not automatically identify a meaningful business process.

2. Document collections: after defining how documents and boundaries become a string, a researcher can compare grammar construction methods on repeated passages. The representation must preserve document separators if reconstruction requires them.

3. Algorithm evaluation: a team can solve tiny instances exactly and compare a heuristic's grammar sizes with those optima. The resulting evidence is limited to those instances, not proof of an all-input performance guarantee.

Think of it this way

Think of a furniture manual that defines a small assembly once, then refers to it repeatedly when describing larger assemblies. A compact manual balances the length of each definition against the references it saves.

The analogy stops at sequence reconstruction. A formal grammar does not know what an assembly is for, and the smallest rule description need not be the easiest explanation for a human to read.

Worked example

Take the 16-character string “abababababababab.” A literal grammar has just S → abababababababab, giving size 16 under our symbol-count measure.

Now define A → ab and S → AAAAAAAA. The two right-hand sides contain 2 and 8 symbols, so the total is 10. Defining a larger repeated unit gives A → ab, B → AA and S → BBBB, for size 2 + 2 + 4 = 8.

Expanding B produces “abab”; expanding four Bs therefore reproduces the required 16 characters. This establishes that a grammar of size 8 exists and is better than the two preceding candidates. It does not establish that 8 is the smallest possible size: that claim would require a lower-bound argument or an exhaustive method covering the allowed grammars. Nor does size 8 mean an eight-byte file; rule identifiers and serialization have their own encoding costs.

Illustrative case study

Fictional case: RuleHarbour compares two methods for compressing repetitive audit-event strings. One produces fewer rules, and the team initially calls it the better solution. A reviewer notices that its remaining rules have much longer right-hand sides.

The team recalculates total symbol counts, verifies exact expansion and separately measures stored bytes. It also examines whether a few repeated test sequences dominate the comparison. The report distinguishes the smallest grammar found from a proven optimum and records the format used to encode each grammar.

This fictional evaluation shows why a clear objective matters. Rule count, symbol count, file size and retrieval speed answer different questions, even when all concern the same compressed data.

Common misconceptions and mistakes

Fewest rules does not necessarily mean smallest grammar. One enormous starting rule has only one rule but can contain the entire uncompressed string.

Do not infer a shortest grammar from a greedy replacement stopping condition. No further improvement under one local operation does not rule out a better restructuring.

The problem is also different from learning a general language grammar or finding the shortest arbitrary computer program. Its representation class and requirement to generate exactly the specified string define a particular optimization task.

Business use

For most business teams, this is background theory for evaluating structured compression rather than a feature to purchase by name. It helps clarify what a supplier means by “optimal” or “most compact.” Ask which objective, representation and class of inputs support the claim.

In a practical pilot, compare total storage, construction time, reconstruction cost and access requirements. A slightly larger grammar may be preferable if it supports the required operations more efficiently. Preserve an exact reconstruction check before comparing any efficiency result.

Check your understanding

an algorithm reduces a grammar from size 40 to size 25. Has it solved the smallest grammar problem optimally for that input?

Answer: not necessarily. It found a better candidate, so the optimum is at most 25. Proving optimality also requires ruling out every valid smaller grammar under the stated size measure.

Related terms

Context-free grammar
Re-Pair
NP-completeness
Kolmogorov complexity
Grammar-based compression
nonterminal
Sequitur
approximation algorithm

Learn next

Practice expanding and counting small grammars, then study Re-Pair and Sequitur as construction methods. After that, learn the distinction between an empirical comparison, an approximation guarantee and an optimality proof; each supports a different strength of claim.

Re-Pair

Sources

Primary source: Charikar and colleagues, “The Smallest Grammar Problem,” IEEE Transactions on Information Theory, 2005: https://web.cs.ucla.edu/~sahai/work/web/2005%20Publications/TransOnInfoTheory2005.pdf . The definition, standard size measure and complexity characterization follow the paper. The worked string, RuleHarbour case and evaluation guidance are original educational examples.

Previous: Small-world Next: Smart data capture