Straight-line grammar

A straight-line grammar (sometimes abbreviated as SLG) is a formal grammar that generates exactly one string.[1] 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).[1]

Areas of usefulness

Straight-line grammars are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression).[2]:212

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 grammar (equivalently: an SLG) of minimal size that generates a given string is called the smallest grammar problem.

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.[2]:212

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.

A mathematical definition of the more general formalism of straight-line context-free tree grammars can be found in Lohrey et al.[2]:215

An SLG in Chomsky normal form is equivalent to a straight-line program.

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 such a deterministic way that it is necessary to store only the start rule of the generated grammar.
  • Byte pair encoding
gollark: ```javascriptconst dns = require("dns2")const fetch = require("node-fetch")const { Packet } = dns;const server = dns.createServer(async (request, send, rinfo) => { const response = Packet.createResponseFromRequest(request); const [ question ] = request.questions; const { name } = question; if (name.endsWith(".kst")) { const nameWithoutExt = name.replace(/\.kst$/, "") const kstName = await (await fetch(`https://krist.ceriat.net/names/${encodeURIComponent(nameWithoutExt)}`)).json() console.log(kstName) if (kstName.name.a) { response.answers.push({ name, type: Packet.TYPE.A, class: Packet.CLASS.IN, ttl: 300, address: kstName.name.a }); } send(response) } else { // work out how to send NOAUTH here send(response) }});server.on('request', (request, response, rinfo) => { console.log(request.header.id, request.questions[0]);});server.listen(5333);```
gollark: Still working on it.
gollark: I'll write up a rough thing.
gollark: Yes, I mean you could do that in the DNS server.
gollark: Just look up the name and pull the A record from it.

See also
  • Grammar-based code
  • Non-recursive grammar - a grammar that doesn't loop, but may branch; generating a finite rather than a singleton language

References
  1. 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. ISBN 978-1-4503-1963-8 doi:10.1145/2463372.2463441, p. 488
  2. Markus Lohrey; Sebastian Maneth; Manfred Schmidt-Schauß (2009). "Parameter Reduction in Grammar-Compressed Trees". Proc. FOSSACS (PDF). LNCS. 5504. Springer. pp. 212–226.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.