211
правок
Изменения
м
→Алгоритм
Алгоритм удаления цепных правил из грамматики:
#Найти все цепные пары в грамматике <tex>G\Gamma</tex>.#Для каждой цепной пары <tex>(A,B)</tex> добавить к правилам в грамматику <tex>G_1\Gamma_1</tex> все правила вида <tex>A\rightarrow\alpha</tex>, где <tex>B\rightarrow\alpha</tex> {{---}} нецепное правило из <tex>G\Gamma</tex>.
Найти все цепные пары можно по индукции:
'''Индукция.''' Если пара <tex>(A,B)</tex> {{---}} цепная, и есть правило <tex>B\rightarrow C</tex>, то <tex>(A,C)</tex> {{---}} цепная пара.
Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики <tex>G\Gamma</tex>, и только их.
==Корректность алгоритма==
