23
правки
Изменения
Нет описания правки
Где нетерминалы <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>. Каждый набор правил либо будет применён полностью, либо не будет применён полностью
Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.
}}
{{Утверждение
|statement=Любая контекстно-зависимая грамматика является неукорачивающей.
|proof= Так как в определении контекстно-зависимой грамматики <tex>\gamma</tex> не пуста, то <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>, а поэтому эта грамматика является неукорачивающей.
}}
