Изменения
→Алгоритм
}}
=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{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>. Для каждого такого правила создадим цепную пару.<br>Теперь множество цепных пар будет состоять из <tex>(A, A)</tex> и <tex>(B, B)</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>(A, B)</tex> и <tex>(B, C)</tex>.
# Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(A, B)</tex>, и получем множество <tex>\lbrace (A, A), (A, B), (A, C), (B, B), (B, C) \rbrace</tex>.
# Для каждой пары добавим в <tex>\Gamma'</tex> новые правила:
#* <tex>A\rightarrow a</tex> для <tex>(A, A)</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 b</tex> для <tex>(B, B)</tex>
#* <tex>B\rightarrow c</tex> и <tex>B\rightarrow DD</tex> для <tex>(B, C)</tex>
#* <tex>C\rightarrow c</tex> и <tex>C\rightarrow DD</tex> для <tex>(C, C)</tex>
==Литература==
