Изменения

Грамматика <tex>\Gamma</tex> - неукорачивающая, если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex>(возможно правило <tex>S -> \epsilon</tex>, но тогда S встречается в правых частях правил).

Грамматика <tex>\Gamma</tex> - контекстно-зависимая, если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\alphabeta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста.  Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>. Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots \X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>добавим в <tex>\Gamma_2</tex> следующий набор правил:<tex>X_1 X_2 \ldots \X_n \to Z_1 Y_2 \ldots Y_m</tex><tex>Z_1 X_2 \ldots \X_n \to Z_1 Z_2 \ldots Y_m</tex><tex>\ldots<\tex><tex>Z_1 Z_2 \ldots \Z_{n-1} \X_n \to Z_1 Z_2 \ldots Z_n \ldots Z_m</tex>