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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
  
 
Теперь у нас остались только правила вида <tex>A \rightarrow BC</tex>, <tex>A \rightarrow bc</tex> и <tex>S \rightarrow \varepsilon</tex> (при условии, что <tex>S</tex> не содержится в правых частях правил). Грамматика, содержащая правила только такого вида, называется грамматикой в '''нормальной форме Хомского'''.
 
Теперь у нас остались только правила вида <tex>A \rightarrow BC</tex>, <tex>A \rightarrow bc</tex> и <tex>S \rightarrow \varepsilon</tex> (при условии, что <tex>S</tex> не содержится в правых частях правил). Грамматика, содержащая правила только такого вида, называется грамматикой в '''нормальной форме Хомского'''.
 +
 +
Заметим, что любую контекстно-свободную грамматику можно привести к нормальной форме Хомского. Такая форма грамматики очень удобна для работы многих алгоритмов над грамматиками.

Версия 20:55, 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] не содержится в правых частях правил)

Избавимся от правил, в правых частях которых записаны два символа, один из которых является терминалом, то есть правил вида [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_с[/math] и [math]N_c \rightarrow c[/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 bc[/math] и [math]S \rightarrow \varepsilon[/math] (при условии, что [math]S[/math] не содержится в правых частях правил). Грамматика, содержащая правила только такого вида, называется грамматикой в нормальной форме Хомского.

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