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