Изменения

|statement=Для любой [[Иерархия Хомского формальных грамматик#Класс 1 | неукорачивающей ]] грамматики <tex>\Gamma_1</tex> существует эквивалентная [[Иерархия Хомского формальных грамматик#Класс 1 |контекстно-зависимая ]] грамматика <tex>\Gamma_2</tex>.

Рассмотрим правило из <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> следующий набор заменим набором следующих правил:

\begin{tabular}{rcl}$X_1 X_2 X_3 \ldots X_n$ & $\to$&$ Z_1 X_2 X_3 \ldots X_n$,\\$Z_1 X_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 X_3 \ldots X_n$,\\$Z_1 Z_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 Z_3 \ldots X_n$,\\&$\ldots$&vdots\\$Z_1 Z_2 \ldots Z_{n-1} X_n$ &$\to$& $Z_1 Z_2 \ldots Z_{n-1} Z_n$,\\$Z_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Z_2 Z_3 \ldots Z_n$,\\$Y_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Z_3 \ldots Z_n$,\\$Y_1 Y_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Y_3 \ldots Z_n$,\\&$\ldots$&vdots\\$Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n$&$\to$& $Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m$\.\\end{tabular}

Где Причём нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>и <tex>Z_{*} \notin N_1</tex>.

В словах языка , задаваемого грамматикой , не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 X_2 \ldots Y_mX_n</tex>, то в последствии впоследствии должны быть применены все остальные правила. В противном случае нетерминалы <tex>Z_1</tex> или <tex>Z_n</tex> будут присутствовать в выведенном слове.

Получившаяся грамматика Правила вида <tex>$K$ \Gamma_2</tex> является эквивалентной грамматике <tex>to \Gamma_1varepsilon</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку где <tex>Y_1 Y_2 $K$ \ldots Y_min N_1</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> является контекстно-зависимой.

 {{УтверждениеЛемма|id= ==lemma==

|proof= Так как Заметим, что в [[Иерархия Хомского формальных грамматик#Класс 1|определении контекстно-зависимой грамматики ]] <tex>\gamma</tex> не пуста, то поэтому <tex>|\alpha A \beta| \ge leqslant |\alpha \gamma \beta|</tex>. Следовательно, а поэтому эта такая грамматика является неукорачивающейпо [[Иерархия Хомского формальных грамматик#Класс 1|определению]].

Таким образом, из того что по для любой неукорачивающей грамматике грамматики можно построить эквивалентную ей контекстно-зависимую, и наоборот а любая контекстно-зависимая грамматика является неукорачивающей. Значит, следуетэти грамматики задают один и тот же класс языков. == См. также == * [[Иерархия Хомского формальных грамматик]] <br \>* [[Формальные грамматики]] == Источники информации ==* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, что множества языков задаваемых этими видами грамматик совпадаюти вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)* [https://ru.wikipedia.org/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%8F_%D0%A5%D0%BE%D0%BC%D1%81%D0%BA%D0%BE%D0%B3%D0%BE Википедия {{---}} Иерархия Хомского]* [https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D0%BE-%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0 Википедия {{---}} Контекстно-зависимая грамматика] [[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]][[Категория: Базовые понятия о грамматиках]]