Изменения

|statement=Для любой [[Иерархия Хомского формальных грамматик#Класс 1 | неукорачивающей ]] грамматики <tex>\Gamma_1</tex> существует эквивалентная [[Иерархия Хомского формальных грамматик#Класс 1 |контекстно-зависимая ]] грамматика <tex>\Gamma_2</tex>.

Рассмотрим правило из <tex>\Gamma_1= \langle \Sigma, N_1, S \in N_1, P \in N_1^{*}\times (\Sigma\cup N_1)^{*}\rangle</tex>, оно имеет вид . Будем строить правила для грамматики <tex>\Gamma_2</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_2Gamma_1</tex> следующий набор заменим набором следующих правил:.

Где Причем нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>и <tex>Z_{*} \notin N_1</tex>.

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n</tex>, то в последствии впоследствии должны быть применены все остальные правила. В противном случае нетерминалы <tex>Z_1</tex> или <tex>Z_n</tex> будут присутствовать в выведенном слове.

Получившаяся грамматика Правида вида <tex>$S$ \Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения набора правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 to \ldots Y_mvarepsilon</tex>оставляем без изменений. Каждый набор правил либо будет применён полностью, либо не будет применён полностью

По [[Иерархия Хомского формальных грамматик#Класс 1|определению]] в <tex>\Gamma_1</tex> нет правил другого вида. Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения набора правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Осталось заметить, что по [[Иерархия Хомского формальных грамматик#Класс 1|определению]] получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.

|proof= Так как Заметим, что в [[Иерархия Хомского формальных грамматик#Класс 1|определении контекстно-зависимой грамматики ]] <tex>\gamma</tex> не пуста, то поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>, а поэтому эта . Следовательно такая грамматика является неукорачивающейпо [[Иерархия Хомского формальных грамматик#Класс 1|определению]].

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