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