Нормальная форма Хомского — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
Рассмотрим [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободную грамматику]] <tex>\Gamma</tex>, из которой удалены [[Удаление бесполезных символов из грамматики|бесполезные символы]], [[Удаление eps-правил из грамматики|<tex>\varepsilon</tex>-правила]], [[Удаление длинных правил из грамматики|длинные правила]] и [[Удаление цепных правил из грамматики|цепные правила]].
+
Рассмотрим [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободную грамматику]] <tex>\Gamma</tex>, из которой удалены [[Удаление бесполезных символов из грамматики|бесполезные символы]], [[Удаление eps-правил из грамматики|<tex>\varepsilon</tex>-правила]], [[Удаление длинных правил из грамматики|длинные правила]] и [[Удаление цепных правил из грамматики|цепные правила]]. Такая грамматика содержит только правила следующего вида:
 +
*<tex>A \rightarrow BC</tex>
 +
*<tex>A \rightarrow Bc</tex>
 +
*<tex>A \rightarrow bc</tex>
 +
*<tex>A \rightarrow a</tex>
 +
*<tex>S \rightarrow \varepsilon</tex> (при условии, что <tex>S</tex> не содержится в правых частях правил)

Версия 20:09, 11 октября 2010

Рассмотрим контекстно-свободную грамматику [math]\Gamma[/math], из которой удалены бесполезные символы, [math]\varepsilon[/math]-правила, длинные правила и цепные правила. Такая грамматика содержит только правила следующего вида:

  • [math]A \rightarrow BC[/math]
  • [math]A \rightarrow Bc[/math]
  • [math]A \rightarrow bc[/math]
  • [math]A \rightarrow a[/math]
  • [math]S \rightarrow \varepsilon[/math] (при условии, что [math]S[/math] не содержится в правых частях правил)