23
правки
Изменения
Нет описания правки
{{Определение|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex>(возможно правило <tex>S -> \epsilon</tex>, но тогда S не встречается в правых частях правил).}}
{{Определение|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста(возможно правило <tex>S -> \epsilon</tex>, но тогда S не встречается в правых частях правил).}}
{{Теорема|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.|proof=
Рассмотрим правило из <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>
Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
}}
