23
правки
Изменения
Нет описания правки
Грамматика неукорачивающая, если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex>(возможно правило <tex>S -> \epsilon</tex>, но тогда S встречается в правых частях правил).
Грамматика контекстно-зависимая, если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста.
<tex>Y_1 Y_2 \ldots Y_{n-1} Z_n \to Y_1 Y_2 \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>. Каждый набор правил либо будет применён полность, либо не будет применён полностью
Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.
Любая контекстно-зависимая грамматика является неукорачивающей, так как <tex>\gamma</tex> не пуста, а поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>.
Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
