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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 8: Строка 8:
  
 
== Постановка задачи ==
 
== Постановка задачи ==
Пусть  <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая длинные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую длинных правил
+
Пусть  <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая длинные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую длинных правил.
 
== Алгоритм ==
 
== Алгоритм ==

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

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


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


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

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

Алгоритм