Каждая кс-грамматика G=<N,T,P,S> называется грамматикой в нормальной форме Хомского (или в бинарной нормальной форме), если каждое правило из Р имеет один из следующих видов:

            1. А::=ВС, где А,В,С принадлежит N

            2. А::=а, где а принадлежит Т

            3. S::=Эпсилон, если Э принадлежит Л(Ж), причем S не встречается в правых частях правил

 

Существует достаточно простой способ преобразования любой грамматики в нормальную форму Хомского.

Алгоритм  Преобразование к нормальной форме Хомского

Вход : приведенная кс-грамматика G=<N,T,P,S>

Выход: кс-грамматика Ж' в нормальной форме Хомского, эквивалентная Ж, т.е. Л(Ж')=Л(Ж)

Метод: Грамматика строится след. образом

1. Включить в Р' каждое правило из Р вида А::=а

2. Включить в Р' каждое правило из Р вида А::=ВС

3. Включить в Р' каждое правило из Р вида S::=Э

4. Для каждого правила Р вида А::= Х1,Х2, Хn, где n>2 включить в Р' правила

А::=Х1Х2..Хn => А::=Х1В1,

В::=Х2Х3..Хn => В1::=Х2В2,

5. Дляя каждого правила из Р и P' вида А::=Х1Х2, где один из символов Х1 или Х2 - терминалы, включить в Р' правило вида Х1::=а

Тогда искомая грамматика будет в нормальной форме Хомского.

Теорема  Каждая кс-грамматика эквивалентна некоторой грамматике в НФХ.

Док-во основывается на алгоритме преобразования к НФ.

 

Теорема  Если кс-язык не содержит пустого слова Э, то он порождается некоторой грамматикой, в которой каждое правило имеет один из следующих двух видов:

А::=а

А::=ВС, где а принадлежит ; А,В,С принадлежат N.