Нормальная форма Хомского

Материал из Викиконспекты
Перейти к: навигация, поиск

Рассмотрим контекстно-свободную грамматику [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] не содержится в правых частях правил)