Неукорачивающие и контекстно-зависимые грамматики, эквивалентность — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 11 промежуточных версий 5 участников) | |||
Строка 3: | Строка 3: | ||
|proof= | |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 \ | + | Рассмотрим правило из <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 \geqslant n</tex>, из <tex> \Gamma_1</tex> заменим набором следующих правил: |
<tex> | <tex> | ||
− | + | 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,\\ | |
− | + | \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,\\ | |
− | + | \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.\\ | |
− | |||
− | |||
</tex> | </tex> | ||
− | + | Причём нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex> и <tex>Z_{*} \notin N_1</tex>. | |
В словах языка, задаваемого грамматикой, не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n</tex>, то впоследствии должны быть применены все остальные правила. В противном случае нетерминалы <tex>Z_1</tex> или <tex>Z_n</tex> будут присутствовать в выведенном слове. | В словах языка, задаваемого грамматикой, не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n</tex>, то впоследствии должны быть применены все остальные правила. В противном случае нетерминалы <tex>Z_1</tex> или <tex>Z_n</tex> будут присутствовать в выведенном слове. | ||
Строка 32: | Строка 30: | ||
|id= ==lemma== | |id= ==lemma== | ||
|statement=Любая контекстно-зависимая грамматика является неукорачивающей. | |statement=Любая контекстно-зависимая грамматика является неукорачивающей. | ||
− | |proof= Заметим, что в [[Иерархия Хомского формальных грамматик#Класс 1|определении контекстно-зависимой грамматики]] <tex>\gamma</tex> не пуста, поэтому <tex>|\alpha A \beta| \ | + | |proof= Заметим, что в [[Иерархия Хомского формальных грамматик#Класс 1|определении контекстно-зависимой грамматики]] <tex>\gamma</tex> не пуста, поэтому <tex>|\alpha A \beta| \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 Википедия {{---}} Контекстно-зависимая грамматика] | ||
+ | |||
+ | [[Категория: Теория формальных языков]] | ||
+ | [[Категория: Контекстно-свободные грамматики]] | ||
+ | [[Категория: Базовые понятия о грамматиках]] |
Текущая версия на 19:20, 4 сентября 2022
Теорема: |
Для любой неукорачивающей грамматики существует эквивалентная контекстно-зависимая грамматика . |
Доказательство: |
Рассмотрим правило из . Будем строить правила для контекстно-зависимой грамматики . Каждое правило , где , из заменим набором следующих правил:
Причём нетерминалы свои для каждого правила из и .В словах языка, задаваемого грамматикой, не может быть нетерминалов, поэтому если в процессе вывода будет применено правило , то впоследствии должны быть применены все остальные правила. В противном случае нетерминалы или будут присутствовать в выведенном слове.Правила вида По , где оставляем без изменений. определению в нет правил другого вида. Получившаяся грамматика является эквивалентной грамматике , так в результате применения набора правил строка перейдёт в строку . Осталось заметить, что по определению получившаяся грамматика является контекстно-зависимой. |
Лемма: |
Любая контекстно-зависимая грамматика является неукорачивающей. |
Доказательство: |
Заметим, что в определении контекстно-зависимой грамматики не пуста, поэтому . Следовательно, такая грамматика является неукорачивающей по определению. |
Таким образом, для любой неукорачивающей грамматики можно построить эквивалентную ей контекстно-зависимую, а любая контекстно-зависимая грамматика является неукорачивающей. Значит, эти грамматики задают один и тот же класс языков.
См. также
Источники информации
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
- Википедия — Иерархия Хомского
- Википедия — Контекстно-зависимая грамматика