Изменения

<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$&\\$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$&\\$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>

Где нетерминалы <tex>$Z_{*}$</tex> свои для каждого правила из <tex>Z_1 X_2 X_3 \ldots X_n \to Z_1 Z_2 X_3 \ldots X_nGamma_1</tex>

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

<tex>\ldots</tex> <tex>Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n</tex> <tex>Z_1 Z_2 Z_3 \ldots Z_n \to Y_1 Z_2 Z_3 \ldots Z_n</tex>  <tex>Y_1 Z_2 Z_3 \ldots Z_n \to Y_1 Y_2 Z_3 \ldots Z_n</tex>  <tex>Y_1 Y_2 Z_3 \ldots Z_n \to Y_1 Y_2 Y_3 \ldots Z_n</tex>  <tex>\ldots</tex> <tex>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</tex> Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex> В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминал <tex>Z_1</tex> или <tex>Z_n</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>. Каждый набор правил либо будет применён полность, либо не будет применён полностью