Изменения
Нет описания правки
{{Определение
|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>A \rightarrow BC</tex>
