Изменения

Перейти к: навигация, поиск

Удаление длинных правил из грамматики

86 байт убрано, 05:26, 28 октября 2011
Нет описания правки
Пусть <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>\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>.
=== Корректность алгоритма ===
{{Теорема
69
правок

Навигация