Рост контекстно-зависимой грамматики

редактировать

В теории формального языка, растет контекстно-зависимая грамматика - это контекстно-зависимая грамматика, в которой продукция увеличивает длину генерируемых предложений. Таким образом, эти грамматики неконтрактны и зависят от контекста. растущий контекстно-зависимый язык - это контекстно-зависимый язык, созданный с помощью этих грамматик.

В этих грамматиках "начальный символ" S не появляется с правой стороны любого правила производства, а длина правой стороны каждой продукции превышает длину левой стороны, если только левая сторона is S.

Эти грамматики были введены Дальхаусом и Вармутом. Позже было показано, что они эквивалентны. Членство в любом растущем контекстно-зависимом языке вычислимо за полиномиальное время ; однако равномерная проблема определения того, принадлежит ли данная строка языку, генерируемому данной растущей или ациклической контекстно-зависимой грамматикой, является NP-полной.

См. также

Ссылки

Внешние ссылки

Последняя правка сделана 2021-05-22 11:37:12
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте