Smallest grammar problem¶
Find the least-cost straight-line grammar that generates exactly one specified string.
Core Idea¶
The smallest grammar problem turns lossless grammar-based description into an optimization task. Given one target string, choose a straight-line context-free grammar whose productions generate that string and no other; among such grammars, minimize a declared size measure. Repeated substrings can be named by nonterminals and reused instead of written again.
The cost convention matters. Counting symbols on production right-hand sides differs from also charging for rules, and a grammar that is shorter than one direct production is not thereby proven globally smallest. Computational hardness explains why practical methods often return a small or approximately bounded grammar instead of an exact optimum.
Scope of Application¶
This formal problem applies to exact single-string grammar descriptions under a declared size metric.
- Formal-language theory. Study exact single-string grammars and the cost of their descriptions.
- Lossless compression. Use repeated substrings to construct compact grammar descriptions.
- Approximation algorithms. Compare feasible grammar costs with proven or estimated optimum bounds.
- Pattern extraction. Interpret reusable productions as repeated structure while keeping coding cost explicit.
Clarity¶
A feasible grammar must generate the one target string and no other. Which feasible grammar is 'smallest' depends on the declared rule-cost measure; producing a shorter candidate than a literal rule does not prove global optimality.
Manages Complexity¶
A straight-line grammar compresses repeated substrings into reusable definitions, replacing a long literal sequence with a shorter derivation graph. The optimization problem then compares many possible reuse schemes. This reduces description length when repetitions pay for their rule overhead, but the enormous candidate space makes exact best-choice reasoning difficult.
Abstract Reasoning¶
Fix the string and metric, verify a candidate grammar's unique expansion, and compare the cost of repeated-substring rules against direct text. State whether the result is proven optimal, bounded-approximate, or only heuristic.
Knowledge Transfer¶
The problem transfers literally across strings and alphabets when exact generation and the same cost convention are maintained. General lossless compression shares the goal of short reversible description, but may use dictionaries, coding probabilities, or other objects rather than straight-line grammars. Its optimization skeleton is portable; the one-string grammar feasibility constraint is the domain-specific accent.
Relationships to Other Abstractions¶
Current abstraction Smallest grammar problem Domain-specific
Parents (1) — more general patterns this builds on
-
Smallest grammar problem is a kind of Optimization Prime
Smallest grammar problem is a kind of Optimization; Find the least-cost straight-line grammar that generates exactly one specified string.
Hierarchy path (1) — routes to 1 parentless root
- Smallest grammar problem → Optimization
Neighborhood in Abstraction Space¶
Smallest grammar problem sits in a crowded region of the domain-specific corpus (37th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Language Structure & Grammar Formalisms (23 abstractions)
Nearest neighbors
- Optimizing Compiler — 0.89
- Linear Grammar — 0.88
- Productivity (linguistics) — 0.88
- Self-supervised learning — 0.88
- Literal movement grammar — 0.88
Computed from structural-signature embeddings · 2026-10-08