Изменения

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

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

\end{tabular}

</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> будут присутствовать в выведенном слове.

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

[[Категория: Теория формальных языков]]

[[Категория: Контекстно-свободные грамматики]]