Изменения

Грамматика неукорачивающая, если все правила имеют вид {{Теорема|statement=Для любой [[Иерархия Хомского формальных грамматик#Класс 1 | неукорачивающей]] грамматики <tex>\alpha \to \betaGamma_1</tex>, где <tex>существует эквивалентная [[Иерархия Хомского формальных грамматик#Класс 1 |\alpha| \le |\beta|</tex>(возможно правило контекстно-зависимая]] грамматика <tex>S -> \epsilonGamma_2</tex>, но тогда S встречается в правых частях правил).|proof=

Грамматика контекстно-зависимая, если все правила имеют вид Рассмотрим правило из <tex>\alpha A Gamma_1 = \langle \beta Sigma, N_1, S \to in N_1, P \in N_1^{*}\times (\alpha Sigma\gamma cup N_1)^{*}\betarangle</tex>, где . Будем строить правила для контекстно-зависимой грамматики <tex>A\Gamma_2</tex> - нетерминал, . Каждое правило <tex>X_1 X_2 \alphaldots X_n \to Y_1 Y_2 \ldots Y_m</tex> и , где <tex>m \betageqslant n</tex> строки , из нетерминалов, <tex>\gammaGamma_1</tex> не пуста.заменим набором следующих правил:

Для любой неукорачивающей грамматики Причём нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика и <tex>Z_{*} \Gamma_2notin N_1</tex>.

Рассмотрим В словах языка, задаваемого грамматикой, не может быть нетерминалов, поэтому если в процессе вывода будет применено правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 Z_1 X_2 \ldots Y_mX_n</tex>, где то впоследствии должны быть применены все остальные правила. В противном случае нетерминалы <tex>m \ge nZ_1</tex>добавим в или <tex>\Gamma_2Z_n</tex> следующий набор правил:будут присутствовать в выведенном слове.

Правила вида <tex>X_1 X_2 $K$ \ldots X_n to \to Z_1 Y_2 varepsilon</tex>, где <tex>$K$ \ldots Y_min N_1</tex>оставляем без изменений.

По [[Иерархия Хомского формальных грамматик#Класс 1|определению]] в <tex>Z_1 \Gamma_1</tex> нет правил другого вида. Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения набора правил строка <tex>X_1 X_2 \ldots X_n \to Z_1 Z_2 </tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Осталось заметить, что по [[Иерархия Хомского формальных грамматик#Класс 1|определению]] получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.}}

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

<tex>Z_1 Z_2 \ldots Z_{nТаким образом, для любой неукорачивающей грамматики можно построить эквивалентную ей контекстно-1} X_n \to Z_1 Z_2 \ldots Z_{nзависимую, а любая контекстно-1} Z_n</tex>зависимая грамматика является неукорачивающей. Значит, эти грамматики задают один и тот же класс языков.

== См. также == * [[Иерархия Хомского формальных грамматик]] <tex>Z_1 \ldots Z_n \to Y_1 Z_2 br \ldots Z_n</tex> * [[Формальные грамматики]]

<tex>\ldots<== Источники информации ==* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)* [https:/tex>/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 Википедия {{---}} Контекстно-зависимая грамматика]

<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>. Вывод[[Категория: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.Базовые понятия о грамматиках]]