Прямая грамматика

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

Области полезности

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

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

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

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

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

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

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

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

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

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

Список алгоритмов, использующих SLG

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

См. также

Код на основе грамматики — алгоритм сжатия данных без потерь.
Нерекурсивная грамматика — грамматика, которая не зацикливается, но может разветвляться; создание конечного, а не одноэлементного языка

Ссылки

^ Jump up to: ^а ^б Флориан Бенц и Тимо Кетцинг, «Эффективная эвристика для решения мельчайших грамматических задач», Материалы пятнадцатой ежегодной конференции по генетическим и эволюционным вычислениям - GECCO '13, 2013. ISBN 978-1-4503-1963-8 два : 10.1145/2463372.2463441 , стр. 488.
^ Jump up to: ^а ^б ^с Маркус Лори; Себастьян Манет; Манфред Шмидт-Шаус (2009). «Сокращение параметров в деревьях, сжатых грамматикой». Учеб. ФОССАКС (PDF) . ЛНКС. Том. 5504. Спрингер. стр. 212–226.

[GECCO-1] Jump up to: ^а ^б Флориан Бенц и Тимо Кетцинг, «Эффективная эвристика для решения мельчайших грамматических задач», Материалы пятнадцатой ежегодной конференции по генетическим и эволюционным вычислениям - GECCO '13, 2013. ISBN 978-1-4503-1963-8 два : 10.1145/2463372.2463441 , стр. 488.

[Lohrey.Maneth.Schmidt.2009-2] Jump up to: ^а ^б ^с Маркус Лори; Себастьян Манет; Манфред Шмидт-Шаус (2009). «Сокращение параметров в деревьях, сжатых грамматикой». Учеб. ФОССАКС (PDF) . ЛНКС. Том. 5504. Спрингер. стр. 212–226.

[1]

[2]