Изменения

Рассмотрим правило из <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 geqslant n</tex> , из <tex> \Gamma_1</tex> заменим набором следующих правил:

\begin{tabular}{rcl}$X_1 X_2 X_3 \ldots X_n$ & $\to$&$ Z_1 X_2 X_3 \ldots X_n,$\\$Z_1 X_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 X_3 \ldots X_n,$\\$Z_1 Z_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 Z_3 \ldots X_n,$\\&$\ldots,$&vdots\\$Z_1 Z_2 \ldots Z_{n-1} X_n$ &$\to$& $Z_1 Z_2 \ldots Z_{n-1} Z_n,$\\$Z_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Z_2 Z_3 \ldots Z_n,$\\$Y_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Z_3 \ldots Z_n,$\\$Y_1 Y_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Y_3 \ldots Z_n,$\\&$\ldots,$&vdots\\$Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n$&$\to$& $Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m,$.\\\end{tabular}

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

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