A straight-line grammar (sometimes abbreviated as SLG) is a
formal grammar
In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the language's syntax. A grammar does not describe ...
that generates exactly one string.
[Florian Benz and Timo Kötzing, “An effective heuristic for the smallest grammar problem,” Proceedings of the fifteenth annual conference on Genetic and evolutionary computation conference - GECCO ’13, 2013. , p. 488] 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'').
Areas of usefulness
Straight-line grammars are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression).
SLGs are of interest in fields like
Kolmogorov complexity
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produ ...
,
Lossless data compression
Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistic ...
,
Structure discovery
A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...
and
Compressed data structures.
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 In data compression and the theory of formal languages, the smallest grammar problem is the problem of finding the smallest context-free grammar that generates a given string of characters (but no other string). The size of a grammar is defined by s ...
.
Straight-line grammars (more precisely: straight-line context-free string grammars) can be generalized to ''Straight-line context-free tree grammars''.
The latter can be used conveniently to compress
trees
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
.
Formal Definition
A
context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form
:A\ \to\ \alpha
with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be em ...
''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
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
''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.
A mathematical definition of the more general formalism of straight-line context-free tree grammars can be found in Lohrey et al.
An SLG in
Chomsky normal form
In formal language theory, a context-free grammar, ''G'', is said to be in Chomsky normal form (first described by Noam Chomsky) if all of its production rules are of the form:
: ''A'' → ''BC'', or
: ''A'' → ''a'', or
: ''S'' → ...
is equivalent to a
straight-line program In mathematics, more specifically in computational algebra, a straight-line program (SLP) for a finite group ''G'' = ⟨''S''⟩ is a finite sequence ''L'' of elements of ''G'' such that every element of ''L'' either belongs to ''S'', i ...
.
A list of algorithms using SLGs
* The
Sequitur algorithm Sequitur (or Nevill-Manning algorithm) is a recursive algorithm developed by Craig Nevill-Manning and Ian H. Witten in 1997 that infers a hierarchical structure (context-free grammar) from a sequence of discrete symbols. The algorithm operates in ...
constructs a straight-line grammar for a given string.
* The
Lempel-Ziv-Welch algorithm creates a context-free grammar in such a deterministic way that it is necessary to store only the start rule of the generated grammar.
*
Byte pair encoding
See also
*
*
Non-recursive grammar - a grammar that doesn't loop, but may branch; generating a finite rather than a singleton language
References
{{reflist
Formal languages