65
правок
Изменения
Нет описания правки
Наличие цепных правил в грамматике может усложнять доказательства теорем и давать излишние шаги в выводах слов. Научимся удалять цепные правила из грамматики.
==Алгоритм==
{{Определение
|definition=
}}
Алгоритм удаления цепных правил из грамматики:
Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики <tex>G</tex>, и только их.
==Корректность алгоритма=={{Теорема|statement=Для любой [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматики]] <tex>G</tex> существует эквивалентная ей [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматика]] <tex>G_1</tex> без цепных правил.|proof= Докажем, что, если грамматика <tex>G_1</tex> построена по грамматике <tex>G</tex> с помощью данного описанного выше алгоритма, то <tex>L(G_1)=L(G)</tex>, то есть <tex>w\in L(G_1)</tex> тогда и только тогда, когда <tex>w\in L(G)</tex>.
''Достаточность.'' Предположим, <tex>S\Rightarrow _{G_1}^* w</tex>. Так как каждое правило <tex>G_1</tex> эквивалентно последовательности из нуля или нескольких цепных правил <tex>G</tex>, за которой следует нецепное правило из <tex>G</tex>, то из <tex>\alpha\Rightarrow _{G_1}\beta</tex> следует <tex>\alpha\Rightarrow _G^*\beta</tex>. Таким образом, каждый шаг порождения в <tex>G_1</tex> может быть заменен одним или несколькими шагами в <tex>G</tex>. Собрав эти последовательности шагов, получим, что <tex>S\Rightarrow _G^* w</tex>.
''Необходимость.'' Предположим, что <tex>w\in L(G)</tex>. Тогда <tex>w</tex> имеет левое порождение <tex>S\Rightarrow _{lm}^* w</tex>. Где бы, в левом порождении, не использовалась ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в <tex>G</tex> можно разбить на последовательность "шагов", в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой "шаг". Но по построению <tex>G_1</tex> каждый из этих шагов может быть выполнен одним ее правилом. Таким образом, <tex>S\Rightarrow _{G_1}^* w</tex>.
}}
==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
