Удаление длинных правил из грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
}}  
 
}}  
  
−
'''Постановка задачи.'''
+
== Постановка задачи ==
−
Пусть задана [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]] <tex>\Gamma</tex>. И пусть существует правило вида:
+
Пусть <tex>\Gamma</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>.
 

Версия 22:33, 26 октября 2011

Задача удаления длинных правил из грамматики возникает при попытке ее приведения к нормальной форме Хомского.


Определение:
Пусть [math]\Gamma[/math] — контекстно-свободная грамматика. Правило [math]A \rightarrow \beta [/math] называется длинным если [math]|\beta| \gt 2[/math]


Постановка задачи

Пусть [math]\Gamma[/math] — контекстно-свободная грамматика, содержащая длинные правила. Требуется построить эквивалентную грамматику [math]\Gamma'[/math], не содержащую длинных правил

Алгоритм

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Удаление_длинных_правил_из_грамматики&oldid=12094»