Straight-line grammar

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

Formal Definition[edit]

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 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.[1]

An SLG in Chomsky normal form is equivalent[clarification needed] to a straight-line program.

A list of algorithms using SLGs[edit]

See also[edit]

  1. ^ Markus Lohrey, Sebastian Maneth, Manfred Schmidt-Schauß (2009). "Parameter Reduction in Grammar-Compressed Trees". Proc. FOSSACS. LNCS 5504. Springer. pp. 212–226.  Here: p.215, Sect.2