69
правок
Изменения
Нет описания правки
<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>.
=== Корректность алгоритма ==={{Теорема|statement=Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]]. <tex>\Gamma'</tex> {{---}} грамматика, полученная в результате применения алгоритма к <tex>\Gamma</tex>. Тогда <tex>L(\Gamma) = L(\Gamma')</tex>|proof=<tex>\Rightarrow </tex> <br>Покажем, что <tex>L(\Gamma) \subset L(\Gamma')</tex> <br>Пусть <tex>w \in L(\Gamma)</tex>. Рассмотрим вывод <tex>w</tex>. Если в выводе используется длинное правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>, то заменим его на последовательное применение правил <tex>A \rightarrow a_1B_1</tex>, <tex>B_1 \rightarrow a_2B_2</tex>, <tex>B_2 \rightarrow a_3B_3</tex>, <tex>\ldots </tex>, <tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex>. Получим вывод <tex>w</tex> в <tex>\Gamma'</tex> <br><tex>\Leftarrow </tex> <br>Покажем, что <tex>L(\Gamma') \subset L(\Gamma)</tex> <br>Допустим, что это не так, и <tex>\exists w \in L(\Gamma'), w \notin L(\Gamma)</tex>. <br> Рассмотрим вывод <tex>w</tex> в <tex>L(\Gamma')</tex>.Найдем в этом выводе первое применение правила <tex>A \rightarrow a_1A_1, a_1 \in \Sigma \cup N</tex>, которого нет в <tex>\Gamma</tex>. В ходе алгоритма оно получено из некоторого длинного правила <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>. Применим правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex> вместо <tex>A \rightarrow a_1A_1</tex>, и удалим в выводе все применения правил, полученных из <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>.Такое преобразование уменьшит в выводе <tex>w</tex> количество правил, которых нет в <tex>\Gamma</tex>. Будем повторять это преобразование, пока не получим вывод <tex>w</tex> в <tex>\Gamma</tex>}}
== Пример работы ==
Покажем, как описанный алгоритм будет работать на следующей грамматике: <br>
<tex>A_2 \rightarrow bB</tex> <br>
Для правила <tex>B \rightarrow def</tex> вводим 1 новыq новый нетерминал <tex>B_1</tex>, и 2 новых правила: <br>
<tex>B \rightarrow dB_1</tex> <br>
<tex>B_1 \rightarrow ef</tex> <br>
