Rovná gramatika - Straight-line grammar - Wikipedia

A přímá gramatika (někdy zkráceně SLG) je a formální gramatika který vygeneruje přesně jeden řetězec.^[1] V důsledku toho se nevětví (každý neterminál má pouze jedno přidružené produkční pravidlo) ani smyčku (pokud není terminál A se objevuje v derivaci B, pak B se neobjevuje v derivaci A).^[1]

Oblasti užitečnosti

Lineární gramatiky jsou široce používány při vývoji algoritmů, které se provádějí přímo na komprimovaných strukturách (bez předchozí dekomprese).^[2]^:212

SLG jsou zajímavé v oblastech jako Kolmogorovova složitost, Bezztrátová komprese dat, Objev struktury a Komprimované datové struktury.^{[je zapotřebí objasnění ]}

Problém nalezení bezkontextové gramatiky (ekvivalentně: SLG) minimální velikosti, která generuje daný řetězec, se nazývá nejmenší gramatická úloha.^{[Citace je zapotřebí ]}

Lineární gramatiky (přesněji: lineární bezkontextové řetězcové gramatiky) lze zobecnit na Přímé bezkontextové stromové gramatikyTen lze pohodlně použít ke kompresi stromy.^[2]^:212

Formální definice

A bezkontextová gramatika G je SLG, pokud:

1. pro každý neterminál N, existuje nanejvýš jedno produkční pravidlo, které má N jako jeho levá strana a

2. the řízený graf G=<PROTI,E>, definováno PROTI je souborem terminálů a (A,B) ∈ E kdykoli B se objeví na pravé straně produkčního pravidla pro A, je acyklický.

Matematickou definici obecnějšího formalizmu lineárních bezkontextových stromových gramatik lze najít v Lohrey et al.^[2]^:215

SLG dovnitř Chomsky normální forma je ekvivalentní a přímočarý program.^{[Citace je zapotřebí ]}

Seznam algoritmů využívajících SLG

The Sekvenční algoritmus vytvoří přímou gramatiku pro daný řetězec.
The Algoritmus Lempel-Ziv-Welch vytvoří bezkontextovou gramatiku takovým deterministickým způsobem, že je nutné uložit pouze počáteční pravidlo generované gramatiky.
Kódování bajtových párů

Viz také

Gramatický kód
Nerekurzivní gramatika - gramatika, která neprotíná, ale může se větvit; generování konečného spíše než singletonského jazyka

Reference

^ ^A ^b Florian Benz a Timo Kötzing, „Efektivní heuristika pro nejmenší gramatický problém,“ Sborník z patnáctého ročníku konference o konferenci Genetické a evoluční výpočty - GECCO ’13, 2013. ISBN 978-1-4503-1963-8 doi:10.1145/2463372.2463441, str. 488
^ ^A ^b ^C Markus Lohrey; Sebastian Maneth; Manfred Schmidt-Schauß (2009). "Snížení parametrů u stromů komprimovaných gramatikou". Proc. FOSSACS (PDF). LNCS. 5504. Springer. 212–226.

[GECCO-1] A ^b Florian Benz a Timo Kötzing, „Efektivní heuristika pro nejmenší gramatický problém,“ Sborník z patnáctého ročníku konference o konferenci Genetické a evoluční výpočty - GECCO ’13, 2013. ISBN 978-1-4503-1963-8 doi:10.1145/2463372.2463441, str. 488

[Lohrey.Maneth.Schmidt.2009-2] A ^b ^C Markus Lohrey; Sebastian Maneth; Manfred Schmidt-Schauß (2009). "Snížení parametrů u stromů komprimovaných gramatikou". Proc. FOSSACS (PDF). LNCS. 5504. Springer. 212–226.

[1]

[2]