Straight-line grammar

[1] Straight-line grammars are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression).

[2]: 212 SLGs are of interest in fields like Kolmogorov complexity, Lossless data compression, Structure discovery and Compressed data structures.

[clarification needed] The problem of finding a context-free grammar (equivalently: an SLG) of minimal size that generates a given string is called the smallest grammar problem.

[2]: 212 A context-free grammar G is an SLG if: 1. for every non-terminal N, there is at most one production rule that has N as its left-hand side, and 2. the directed graph G=, defined by V being the set of non-terminals and (A,B) ∈ E whenever B appears at the right-hand side of a production rule for A, is acyclic.

A mathematical definition of the more general formalism of straight-line context-free tree grammars can be found in Lohrey et al.[2]: 215 An SLG in Chomsky normal form is equivalent to a straight-line program.