Straight-line grammar

Straight-line grammar

Straight-line grammars (SLG) are formal grammars that do not branch (every non-terminal has only one associated production rule) nor loop (if non-terminal A appears in a derivation of B, B does not appear in a derivation of A). Such grammars generate only one sequence, and this property makes them of interest in fields like Kolmogorov complexity, Lossless data compression, Structure discovery and Compressed data structure.

The problem of finding a SLG of minimal size is called the Smallest grammar problem.

A Grammar G is a SLG iif:

1. for every non-terminal N, there is at most one production rule that has N as its left-hand side

2. take the graph G = < V,E > , with V the set of non-terminals and (A,B) \in E if B appears at the right-hand side of a production rule for A. G must be acyclic.

A SLG in Chomsky normal form is equivalent to a straight-line program. In general, the only type of grammar that are considered are context-free grammar.

  • Sequitur
  • 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



Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Main North railway line, New South Wales — For other railways called Main North Line, see Main North Line. For other railways called Great Northern, see Great Northern Railway. [v · d · …   Wikipedia

  • HEBREW GRAMMAR — The following entry is divided into two sections: an Introduction for the non specialist and (II) a detailed survey. [i] HEBREW GRAMMAR: AN INTRODUCTION There are four main phases in the history of the Hebrew language: the biblical or classical,… …   Encyclopedia of Judaism

  • The Thin Blue Line (TV series) — infobox television show name = The Thin Blue Line caption = The Complete Thin Blue Line DVD format = Sitcom runtime = 30 minutes creator = starring = Rowan Atkinson James Dreyfus Mina Anwar Serena Evans Rudolph Walker David Haig Kevin Allen Mark… …   Wikipedia

  • Sequitur algorithm — Sequitur (or Nevill Manning algorithm) is a recursive algorithm developed by Craig Nevill Manning and Ian H. Witten in 1997[1] that infers a hierarchical structure (context free grammar) from a sequence of discrete symbols. The algorithm operates …   Wikipedia

  • South Asian arts — Literary, performing, and visual arts of India, Pakistan, Bangladesh, and Sri Lanka. Myths of the popular gods, Vishnu and Shiva, in the Puranas (ancient tales) and the Mahabharata and Ramayana epics, supply material for representational and… …   Universalium

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Irish Literature — • It is uncertain at what period and in what manner the Irish discovered the use of letters. It may have been through direct commerce with Gaul, but it is more probable, as McNeill has shown in his study of Irish oghams, that it was from the… …   Catholic encyclopedia

  • Sentence diagram — X bar theory graph of the sentence He studies linguistics at the university. IP = Inflectional phrase. In pedagogy, a sentence diagram is a pictorial representation of the grammatical structure of a natural language sentence. A sentence diagram… …   Wikipedia

  • mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… …   Universalium

  • Otomi language — Otomi Hñähnü, Hñähño, Hñotho, Hñähü, Hñätho, Yųhų, Yųhmų, Ñųhų, Ñǫthǫ, Ñañhų Otomi market …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”