23
правки
Изменения
Нет описания правки
Для любой неукорачивающей грамматики <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>
