Изменения
Новая страница: «== Удаление длинных правил из грамматики == Задача удаления длинных правил из грамматики в…»
== Удаление длинных правил из грамматики ==
Задача удаления длинных правил из грамматики возникает при попытке ее приведения к [[нормальная форма Хомского|нормальной форме Хомского]].
'''Постановка задачи.'''
Пусть задана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] <tex>\Gamma</tex>. И пусть существует правило вида:
*<tex>A \rightarrow \alpha_1 \alpha_2 ... \alpha_k </tex>.
Требуется получить лишь правила вида:
*<tex>A \rightarrow BC</tex>
'''Удаление длинных правил.'''
Давайте формально перезапишем:
*<tex>A \rightarrow \alpha_1 A_1 </tex>. Тогда:
*<tex>A_1 \rightarrow \alpha_2 A_2</tex>. И т.д.
На <tex>k-1 -</tex>ой итерации получим:
*<tex>A_{k-1} \rightarrow \alpha_k </tex>
Тогда финально получим:
*<tex>A \rightarrow A_{k-2} A_{k-1} </tex>.
Задача удаления длинных правил из грамматики возникает при попытке ее приведения к [[нормальная форма Хомского|нормальной форме Хомского]].
'''Постановка задачи.'''
Пусть задана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] <tex>\Gamma</tex>. И пусть существует правило вида:
*<tex>A \rightarrow \alpha_1 \alpha_2 ... \alpha_k </tex>.
Требуется получить лишь правила вида:
*<tex>A \rightarrow BC</tex>
'''Удаление длинных правил.'''
Давайте формально перезапишем:
*<tex>A \rightarrow \alpha_1 A_1 </tex>. Тогда:
*<tex>A_1 \rightarrow \alpha_2 A_2</tex>. И т.д.
На <tex>k-1 -</tex>ой итерации получим:
*<tex>A_{k-1} \rightarrow \alpha_k </tex>
Тогда финально получим:
*<tex>A \rightarrow A_{k-2} A_{k-1} </tex>.
