69
правок
Изменения
Нет описания правки
{{Определение
|definition =
== Постановка задачи ==
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая длинные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую длинных правил. <br>Задача удаления длинных правил из грамматики возникает при попытке ее приведения к [[нормальная форма Хомского|нормальной форме Хомского]].
== Алгоритм ==
С каждым длинным правилом <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>, <tex>k > 2</tex>, <tex>a_i \in \Sigma \cup N</tex> проделаем следующее: <br>
