62
правки
Изменения
Нет описания правки
{{Теорема
|statement=Для любой [[Иерархия Хомского формальных грамматик#Класс 1 | неукорачивающей ]] грамматики <tex>\Gamma_1</tex> существует эквивалентная [[Иерархия Хомского формальных грамматик#Класс 1 |контекстно-зависимая ]] грамматика <tex>\Gamma_2</tex>.
|proof=
Рассмотрим правило из <tex>\Gamma_1= \langle \Sigma, N_1, S \in N_1, P \in N_1^{*}\times (\Sigma\cup N_1)^{*}\rangle</tex>, оно имеет вид . Будем строить правила для контекстно-зависимой грамматики <tex>\Gamma_2</tex>. Каждое правило <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge geqslant n</tex>добавим в , из <tex>\Gamma_2Gamma_1</tex> следующий набор заменим набором следующих правил:
<tex>
</tex>
По [[Иерархия Хомского формальных грамматик#Класс 1|определению]] в <tex>\Gamma_1</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>. Каждый набор правил либо будет применён полностьюОсталось заметить, либо не будет применён полностьючто по [[Иерархия Хомского формальных грамматик#Класс 1|определению]] получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.}}