Грамматика неукорачивающая, если все правила имеют вид [math]\alpha \to \beta[/math], где [math]|\alpha| \le |\beta|[/math](возможно правило [math]S -\gt \epsilon[/math], но тогда S встречается в правых частях правил).
Грамматика зависимая, если все правила имеют вид [math]\alpha A \beta \to \alpha \gamma \beta[/math], где [math]A[/math] - нетерминал, [math]\alpha[/math] и [math]\beta[/math] строки из нетерминалов, [math]\gamma[/math] не пуста.
Для любой неукорачивающей грамматики [math]\Gamma_1[/math] существует эквивалентная контекстно-зависимая грамматика [math]\Gamma_2[/math].
Рассмотрим правило из [math]\Gamma_1[/math], оно имеет вид [math]X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m[/math], где [math]m \ge n[/math]
добавим в [math]\Gamma_2[/math] следующий набор правил:
[math]X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m[/math]
[math]Z_1 X_2 \ldots X_n \to Z_1 Z_2 \ldots Y_m[/math]
[math]\ldots[/math]
[math]Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n[/math]
[math]Z_1 \ldots Z_n \to Y_1 Z_2 \ldots Z_n[/math]
[math]\ldots[/math]
[math]Y_1 Y_2 \ldots Y_{n-1} Z_n \to Y_1 Y_2 \ldots Y_{n-1} Y_n \ldots Y_m[/math]
