69
правок
Изменения
Нет описания правки
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая длинные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую длинных правил.
== Алгоритм ==
Добавим в грамматику <tex>k - 2</tex> новых нетерминалов <tex>B_1, B_2, \ldots B_{k-2}</tex> <br>
Добавим в грамматику <tex>k-1</tex> новое правило: <br>
<tex>\ldots </tex> <br>
<tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex> <br>
Удалим из грамматики правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>. Проделаем описанную операцию с каждым длинным правилом в <tex>\Gamma</tex>.
=== Корректность алгоритма ===
{{Теорема
