Прямолинейная грамматика - Straight-line grammar

А прямолинейная грамматика (иногда сокращенно SLG) - это формальная грамматика который генерирует ровно одну строку.^[1] Следовательно, он не разветвляется (каждый нетерминал имеет только одно связанное производственное правило) и не зацикливается (если нетерминальный А появляется в выводе B, тогда B не появляется при выводе А).^[1]

Сферы полезности

Прямолинейные грамматики широко используются при разработке алгоритмов, которые выполняются непосредственно на сжатых структурах (без предварительной декомпрессии).^[2]:212

SLG представляют интерес в таких областях, как Колмогоровская сложность, Сжатие данных без потерь, Открытие структуры и Сжатые структуры данных.^{[требуется разъяснение ]}

Проблема поиска контекстно-свободной грамматики (эквивалентно: SLG) минимального размера, которая генерирует данную строку, называется самая маленькая грамматическая проблема.^{[нужна цитата ]}

Прямолинейные грамматики (точнее: прямолинейные контекстно-свободные строковые грамматики) могут быть обобщены на Прямолинейные контекстно-свободные древовидные грамматикиПоследний можно использовать для сжатия деревья.^[2]:212

Формальное определение

А контекстно-свободная грамматика грамм является SLG, если:

1. для каждого нетерминального N, существует не более одного производственного правила, которое N как его левая сторона, и

2. ориентированный граф грамм=<V,E>, определяемый V являясь набором нетерминалов и (А,B) ∈ E в любое время B появляется в правой части производственного правила для А, является ациклический.

Математическое определение более общего формализма прямолинейных контекстно-свободных древовидных грамматик можно найти в Lohrey et al.^[2]:215

SLG в Нормальная форма Хомского эквивалентно прямолинейная программа.^{[нужна цитата ]}

Список алгоритмов с использованием SLG

• В Алгоритм Sequitur строит прямолинейную грамматику для данной строки.
• В Алгоритм Лемпеля-Зива-Велча создает контекстно-свободную грамматику таким детерминированным образом, что необходимо хранить только стартовое правило сгенерированной грамматики.
• Кодирование пар байтов

Смотрите также

• Код на основе грамматики
• Нерекурсивная грамматика - грамматика, которая не зацикливается, но может разветвляться; создание конечного, а не одноэлементного языка

Рекомендации

1. Флориан Бенц и Тимо Кётцинг, «Эффективная эвристика для решения малейшей грамматической проблемы», Материалы пятнадцатой ежегодной конференции по генетическим и эволюционным вычислениям - GECCO ’13, 2013. ISBN  978-1-4503-1963-8 Дои:10.1145/2463372.2463441, п. 488
2. Маркус Лохри; Себастьян Манет; Манфред Шмидт-Шаус (2009). "Уменьшение параметров в сжатых грамматически деревьях". Proc. FOSSACS (PDF). LNCS. 5504. Springer. С. 212–226.