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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Удаление длинных правил из грамматики == Задача удаления длинных правил из грамматики в…»)
 
Строка 1: Строка 1:
== Удаление длинных правил из грамматики ==
+
Задача удаления длинных правил из грамматики возникает при попытке ее приведения к [[нормальная форма Хомского|нормальной форме Хомского]].
  
Задача удаления длинных правил из грамматики возникает при попытке ее приведения к [[нормальная форма Хомского|нормальной форме Хомского]].
+
{{Определение
 +
|definition =
 +
Пусть  <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]].
 +
Правило <tex>A \rightarrow \beta </tex> называется '''длинным''' если <tex>|\beta| > 2</tex>
 +
}}
  
 
'''Постановка задачи.'''
 
'''Постановка задачи.'''

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

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


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


Постановка задачи. Пусть задана контекстно-свободная грамматика [math]\Gamma[/math]. И пусть существует правило вида:

  • [math]A \rightarrow \alpha_1 \alpha_2 ... \alpha_k [/math].

Требуется получить лишь правила вида:

  • [math]A \rightarrow BC[/math]

Удаление длинных правил. Давайте формально перезапишем:

  • [math]A \rightarrow \alpha_1 A_1 [/math]. Тогда:
  • [math]A_1 \rightarrow \alpha_2 A_2[/math]. И т.д.

На [math]k-1 -[/math]ой итерации получим:

  • [math]A_{k-1} \rightarrow \alpha_k [/math]

Тогда финально получим:

  • [math]A \rightarrow A_{k-2} A_{k-1} [/math].