|This article does not cite any references or sources. (April 2010)|
A straight-line grammar (SLG) is a formal grammar that 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). Such a grammar generates only one sequence. This property makes SLGs of interest in fields like Kolmogorov complexity, Lossless data compression, Structure discovery and Compressed data structures.[clarification needed]
The problem of finding an SLG of minimal size that generates a given string is called the Smallest grammar problem.
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
A list of algorithms using SLGs
- The Sequitur algorithm constructs a straight-line grammar for a given string.
- The Lempel-Ziv-Welch algorithm creates a context-free grammar in a such deterministic way that it is necessary to store only the start rule of the generated grammar.
- Byte pair encoding
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|