Изменения

'''Цепное правило''' (''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>, используя только цепные правила.

#Для каждой цепной пары <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>

Докажем, что, если грамматика <tex>G_1\Leftarrow </tex> построена по грамматике <br>Покажем, что <tex>GL(\Gamma') \subseteq 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>O(\left| \Gamma \right| ^ 2)</tex>.'' Предположим,  === Пример ===Рассмотрим грамматику:<tex>S\Rightarrow _begin{G_1array}^* w{l l} A\rightarrow B|a\\ B\rightarrow C|b\\ C\rightarrow DD|c\end{array}</tex>, в которой есть два цепных правила <tex>A\rightarrow B</tex> и <tex>B\rightarrow C</tex>. # Для каждого нетерминала создадим цепную пару. Теперь множество цепных пар будет состоять из <tex>(A, A)</tex>, <tex>(B, B)</tex>, <tex>(C, C)</tex> и <tex>(D, D)</tex>.# Рассмотрим цепное правило <tex>A\rightarrow B</tex>. Так как каждое правило существует цепная пара <tex>G_1(A, A)</tex> эквивалентно последовательности , второй элемент которой совпадает с левым нетерминалом из нуля или нескольких цепных правил правила,<br>добавим в множество пару <tex>G(A, B)</tex>, за у которой следует нецепное правило первый элемент такой же как у найденной, а второй равен правому нетерминалу из текущего правила.# Повторим второй пункт для правила <tex>GB\rightarrow C</tex>и пары <tex>(B, то B)</tex>. Теперь множество цепных пар будет состоять из <tex>(A, A)</tex>, <tex>(B, B)</tex>, <tex>(C, C)</tex>, <tex>(D, D)</tex>, <tex>(A, B)</tex> и <tex>(B, C)</tex>.# Повторим второй пункт для правила <tex>B\alpharightarrow C</tex> и пары <tex>(A, B)</tex>, и получим множество <tex>\Rightarrow _{G_1}lbrace (A, A), (B, B), (C, C), (D, D), (A, B), (B, C), (A, C)\betarbrace</tex> следует .# Для каждой пары добавим в <tex>\alpha\Rightarrow _G^Gamma'</tex> новые правила:#*<tex>A\betarightarrow b</tex>. Таким образомдля <tex>(A, каждый шаг порождения в B)</tex>#* <tex>G_1A\rightarrow c</tex> может быть заменен одним или несколькими шагами в и <tex>GA\rightarrow DD</tex>. Собрав эти последовательности шаговдля <tex>(A, получим, что C)</tex>#* <tex>B\rightarrow c</tex> и <tex>SB\Rightarrow _G^* wrightarrow DD</tex> для <tex>(B, C)</tex>#* Оставшиеся цепные пары новых правил не добавят.

''Необходимость== См.'' Предположимтакже ==* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод, что <tex>w\in L(G)</tex>. Тогда <tex>w</tex> имеет левое порождение <tex>S\Rightarrow _{lm}^_дерево_разбора|Контекстно-свободные грамматики]]* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]* w<[http:/tex>. Где бы в левом порождении ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в <tex>G</tex> можно разбить на последовательность "шагов", в которых ноль или несколько цепных правил сопровождаются нецепнымen. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой "шаг"wikipedia. Но по построению <tex>G_1<org/tex> каждый из этих шагов может быть выполнен одним ее правилом. Таким образом, <tex>S\Rightarrow _{G_1}^* w<wiki/tex>.}}Chomsky_normal_form Chomsky normal form]