Изменения
Нет описания правки
{{Определение
|definition=
'''Цепное правило''' (''unit rule'') — правило вида <tex>A\rightarrow B</tex>, где <tex>A</tex> и <tex>B</tex> — нетерминалы.
}}
{{Определение
|definition=
'''Цепная пара''' (''unit pair'') — упорядоченная пара <tex>(A,B)</tex>, в которой <tex>A\Rightarrow ^* B</tex>, используя только цепные правила.
}}
}}
=== Время работы алгоритма ===
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>.
=== Пример ===
B\rightarrow C|b\\
C\rightarrow DD|c
\end{array}</tex>, в которой есть два цепных правила <tex>A\rightarrow B</tex> и <tex>B\rightarrow C</tex>.
# В этой грамматике два Для каждого нетерминала создадим цепную пару. Теперь множество цепных правила пар будет состоять из <tex>(A, A\rightarrow B)</tex> и , <tex>(B, B\rightarrow C)</tex>. Для каждого такого правила создадим цепную пару.<br>Теперь множество цепных пар будет состоять из , <tex>(AC, AC)</tex> и <tex>(BD, BD)</tex>.
# Рассмотрим цепное правило <tex>A\rightarrow B</tex>. Так как существует цепная пара <tex>(A, A)</tex>, второй элемент которой совпадает с левым нетерминалом из правила,<br>добавим в множество пару <tex>(A, B)</tex>, у которой первый элемент такой же как у найденной, а второй равен правому нетерминалу из текущего правила.
# Повторим второй пункт для правила <tex>B\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\rightarrow C</tex> и пары <tex>(A, B)</tex>, и получим множество <tex>\lbrace (A, A), (AB, B), (AC, C), (D, D), (A, B), (B, C), (BA, C) \rbrace</tex>.
# Для каждой пары добавим в <tex>\Gamma'</tex> новые правила:
#* <tex>A\rightarrow b</tex> для <tex>(A, B)</tex>
#* <tex>A\rightarrow c</tex> и <tex>A\rightarrow DD</tex> для <tex>(A, C)</tex>
#* <tex>B\rightarrow c</tex> и <tex>B\rightarrow DD</tex> для <tex>(B, C)</tex>
#* Пары <tex>(A, A)</tex> и <tex>(B, B)</tex> Оставшиеся цепные пары новых правил не добавят. == См. также ==* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]
==Литература==
