Оглавление
Индексированная грамматика
-
Определение индексированных грамматик
- Индексированные грамматики – это формализм для описания контекстно-зависимых языков.
- Они отличаются от обычных контекстно-зависимых грамматик тем, что содержат индексы, которые указывают на стеки символов.
-
Примеры и свойства
- Индексированные грамматики могут описывать языки, такие как {www: w ∈ {a, b}*} и {an bn cn: n ≥ 1}.
- Они могут быть обобщены на линейно-индексированные грамматики, которые ограничивают количество нетерминалов, получающих стек.
-
Вычислительная мощность и отношение к другим формализмам
- Линейно-индексированные грамматики являются строго менее мощными, чем индексированные грамматики Aho.
- Они могут быть преобразованы в индексированные грамматики Aho, что делает их строго менее мощными.
- Они также могут быть преобразованы в другие формализмы, такие как комбинаторные категориальные грамматики и древовидные грамматики.
-
Грамматики с распределенным индексом
- Распределенные индексные грамматики (DIGs) отличаются от индексированных грамматик Aho тем, что распределяют стек по выбранным нетерминалам.
- Они являются надмножеством языков с линейной индексацией и могут быть преобразованы в них.
Полный текст статьи: