271
правка
Изменения
Нет описания правки
==Несколько определений==
{{Определение
|definition=Грамматикой в нормальной форме Хомского (''Chomsky normal form'') называется грамматика, в которой могут содержатся правила только следующего вида
}}
{{Определение
|definition=Вершина называется обнуляемой, если из нее можно прямо или косвенно получить пустую строку.
Если <tex> A \rightarrow \varepsilon </tex>, то <tex> A </tex> {{---}} обнуляемая.
Если <tex> A \rightarrow B_1....B_n </tex>, где все <tex> B_i </tex> обнуляемые, то <tex> A </tex> тоже обнуляемая.
}}
==Преобразование грамматики в нормальную форму Хомского==
