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