211
правок
Изменения
м
Докажем, что, если грамматика <tex>G_1\Leftarrow </tex> построена по грамматике <br>Покажем, что <tex>GL(\Gamma') \subset L(\Gamma)</tex> с помощью описанного выше алгоритма, то . <br>Пусть <tex>w\in L(G_1)=L(G\Gamma')</tex>, то есть <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>. Так как каждое правило <tex>\Gamma'</tex> эквивалентно последовательности из нуля или нескольких цепных правил <tex>\Gamma</tex>, за которой следует нецепное правило из <tex>\Gamma</tex>, то из <tex>\alpha{\underset{\Gamma'}{\Rightarrow}} \in L(G_1)beta</tex> следует <tex>\alpha\overset{*}{\underset{\Gamma}{\Rightarrow}} \beta</tex>. Таким образом, каждый шаг порождения в <tex>\Gamma'</tex> может быть заменен одним или несколькими шагами в <tex>\Gamma</tex>. Собрав эти последовательности шагов, получим, что <tex>S\overset{*}{\underset{\Gamma}{\Rightarrow}} w</tex> тогда и только тогда, когда то есть <tex>w\in L(G\Gamma)</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>.
→Алгоритм
Алгоритм удаления цепных правил из грамматики:
#Найти все цепные пары в грамматике <tex>\Gamma</tex>.
#Для каждой цепной пары <tex>(A,B)</tex> добавить в грамматику <tex>\Gamma_1Gamma'</tex> все правила вида <tex>A\rightarrow\alpha</tex>, где <tex>B\rightarrow\alpha</tex> {{---}} нецепное правило из <tex>\Gamma</tex>.
Найти все цепные пары можно по индукции:
===Корректность алгоритма===
{{Теорема
|statement=Для любой Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КСконтекстно-грамматикисвободная грамматика]] существует эквивалентная ей [[Контекстно. <tex>\Gamma'</tex> {{-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-}} грамматика]] без цепных правил, полученная в результате применения алгоритма к <tex>\Gamma</tex>. Тогда <tex>L(\Gamma) = L(\Gamma').</tex>
|proof=
<tex>\Rightarrow </tex> <br>
Покажем, что <tex>L(\Gamma) \subset L(\Gamma')</tex>. <br>
Пусть <tex>w\in L(\Gamma)</tex>. Тогда <tex>w</tex> имеет левое порождение <tex>S\overset{*}{\underset{lm}{\Rightarrow}} w</tex>. Где бы в левом порождении ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в <tex>\Gamma</tex> можно разбить на последовательность шагов, в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой шаг. Но по построению <tex>\Gamma'</tex> каждый из этих шагов может быть выполнен одним её правилом. Таким образом, <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma')</tex>.
}}
==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
