Изменения

'''Цепное правило ''' (''unit rule'') — правило вида <tex>A\rightarrow B</tex>, где <tex>A</tex> и <tex>B</tex> — нетерминалы.

Наличие == Постановка задачи ==Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая цепные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую цепных правил в грамматике может усложнять доказательства теорем и давать излишние шаги в выводах слов. Научимся удалять цепные правила <br>Задача удаления цепных правил из грамматикивозникает при попытке её приведения к [[нормальная форма Хомского|нормальной форме Хомского]].

'''Цепная пара ''' (''unit pair'') — упорядоченная пара <tex>(A,B)</tex>, в которой <tex>A\Rightarrow ^* B</tex>, используя только цепные правила.

 1) #Найти все цепные пары в грамматике <tex>G\Gamma</tex>. 2) #Для каждой цепной пары <tex>(A,B)</tex> добавить к правилам в грамматику <tex>G_1\Gamma'</tex> все правила вида <tex>A\rightarrow\alpha</tex>, где <tex>B\rightarrow\alpha</tex> {{---}} нецепное правило из <tex>G\Gamma</tex>.#Удалить все цепные правила

Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики <tex>G\Gamma</tex>, и только их.

Докажем===Корректность алгоритма==={{Теорема|statement=Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, чтовывод, лево- и правосторонний вывод, если дерево разбора|контекстно-свободная грамматика ]]. <tex>G_1\Gamma'</tex> построена по грамматике {{---}} грамматика, полученная в результате применения алгоритма к <tex>G\Gamma</tex> с помощью данного алгоритма, то . Тогда <tex>L(G_1\Gamma)=L(G\Gamma').</tex>|proof=<tex>\Rightarrow </tex> <br>Покажем, то есть что <tex>L(\Gamma) \subseteq L(\Gamma')</tex>. <br>Пусть <tex>w\in L(G_1\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(G\Gamma')</tex>.

<tex>\Leftarrow </tex> <br>Покажем, что <tex>L(\Gamma''Достаточность) \subseteq L(\Gamma)</tex>.<br>Пусть <tex>w\in L(\Gamma'' Предположим)</tex>, то есть <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow _{G_1}^* } w</tex>. Так как каждое правило <tex>G_1\Gamma'</tex> эквивалентно последовательности из нуля или нескольких цепных правил <tex>G\Gamma</tex>, за которой следует нецепное правило из <tex>G\Gamma</tex>, то из <tex>\alpha{\underset{\Gamma'}{\Rightarrow _{G_1}}\beta</tex> следует <tex>\alpha\overset{*}{\underset{\Gamma}{\Rightarrow _G^*}} \beta</tex>. Таким образом, каждый шаг порождения в <tex>G_1\Gamma'</tex> может быть заменен одним или несколькими шагами в <tex>G\Gamma</tex>. Собрав эти последовательности шагов, получим, что <tex>S\overset{*}{\underset{\Gamma}{\Rightarrow _G^* }} w</tex>, то есть <tex>w\in L(\Gamma)</tex>.