A straight-line grammar (sometimes with "straight-line" in scare quotes, also abbreviated as SLG) is a formal grammar that generates exactly one string. Consequently, it does not branch (every non-terminal has only one associated production rule) nor loop (if non-terminal A appears in a derivation of B, then B does not appear in a derivation of A).
Contents
SLGs are of interest in fields like Kolmogorov complexity, Lossless data compression, Structure discovery and Compressed data structures.
The problem of finding a context-free SLG of minimal size that generates a given string is called the smallest grammar problem.
Formal Definition
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=<V,E>, 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.
An SLG in Chomsky normal form is equivalent to a straight-line program.