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