Изменения
Нет описания правки
{{Определение
|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>. Для преобразования ее в нормальную форму Хомского необходимо избавиться от правил следующего типа.
# Создание новой стартовой вершины.
#: Создадим новую стартовую вершину <tex> S_0 </tex> с новым правилом <tex> S_0 \rightarrow S </tex>, где <tex> S </tex> {{---}} старая стартовая вершина.
# Удаление вершин, которые могут породить пустую строку.
#:
# Удаление вершин, которые могут породить друг друга.
# Преобразование правил с длинной правой частью.
