211
правок
Изменения
м
→Алгоритм
== Алгоритм ==
С каждым длинным правилом <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>w</tex> в <tex>\Gamma \cup \Gamma'</tex>, в котором меньше применений правил, отсутствующих в <tex>\Gamma</tex>, чем в исходном. Противоречие.
}}
== Пример работы ==
Покажем, как описанный алгоритм будет работать на следующей грамматике: <br>
