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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
{{Определение
 +
|definition=Грамматикой в нормальной форме Хомского (''Chomsky normal form'') называется грамматика, в которой содержатся правила только следующего вида
 +
<tex>A \rightarrow B C </tex>
 +
 +
<tex>A \rightarrow a </tex>
 +
 +
<tex>S \rightarrow \varepsilon </tex>
 +
 +
(где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка).
 +
}}
 +
 +
 
Рассмотрим [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободную грамматику]] <tex>\Gamma</tex>, из которой удалены [[Удаление бесполезных символов из грамматики|бесполезные символы]], [[Удаление eps-правил из грамматики|<tex>\varepsilon</tex>-правила]], [[Удаление длинных правил из грамматики|длинные правила]] и [[Удаление цепных правил из грамматики|цепные правила]]. Такая грамматика содержит только правила следующего вида:
 
Рассмотрим [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободную грамматику]] <tex>\Gamma</tex>, из которой удалены [[Удаление бесполезных символов из грамматики|бесполезные символы]], [[Удаление eps-правил из грамматики|<tex>\varepsilon</tex>-правила]], [[Удаление длинных правил из грамматики|длинные правила]] и [[Удаление цепных правил из грамматики|цепные правила]]. Такая грамматика содержит только правила следующего вида:
 
*<tex>A \rightarrow BC</tex>
 
*<tex>A \rightarrow BC</tex>

Версия 03:35, 26 октября 2011

Определение:
Грамматикой в нормальной форме Хомского (Chomsky normal form) называется грамматика, в которой содержатся правила только следующего вида

[math]A \rightarrow B C [/math]

[math]A \rightarrow a [/math]

[math]S \rightarrow \varepsilon [/math]

(где [math] a [/math] — терминал, [math] A, B, C [/math] — нетерминалы, [math] S [/math] — стартовая вершина, [math] \varepsilon [/math] — пустая строка).


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

  • [math]A \rightarrow BC[/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] не содержится в правых частях правил)

Избавимся от правил, в правых частях которых записаны два символа, один из которых является терминалом, то есть правил вида [math]A \rightarrow Bc[/math], [math]A \rightarrow bC[/math] и [math]A \rightarrow bc[/math]. Введем для каждого терминала [math]a[/math] "персональный" нетерминал [math]N_a[/math]. Затем правила вида [math]A \rightarrow Bc[/math] заменим парой правил [math]A \rightarrow BN_c[/math] и [math]N_c \rightarrow c[/math], правила вида [math]A \rightarrow bC[/math] заменим парой правил [math]A \rightarrow N_bC[/math] и [math]N_b \rightarrow b[/math], а правила вида [math]A \rightarrow bc[/math] — тройкой правил [math]A \rightarrow N_bN_c[/math], [math]N_b \rightarrow b[/math] и [math]N_c \rightarrow c[/math].

Теперь у нас остались только правила вида [math]A \rightarrow BC[/math], [math]A \rightarrow a[/math] и, возможно, [math]S \rightarrow \varepsilon[/math] (при условии, что [math]S[/math] не содержится в правых частях правил). Грамматика, содержащая правила только такого вида, называется грамматикой в нормальной форме Хомского.

Заметим, что любую контекстно-свободную грамматику можно привести к нормальной форме Хомского. Такая форма грамматики очень удобна для работы многих алгоритмов над грамматиками, например, алгоритм Кока-Янгера-Касами

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Нормальная_форма_Хомского&oldid=11979»