Математическая теория формальных языков
Нормальная форма Хомского
Определение 8.3.1.
Грамматика в нормальной форме Хомского (грамматика в бинарной нормальной форме, квадратичная грамматика, grammar in Chomsky normal form) - контекстно-свободная грамматика , в которой каждое правило имеет один из следующих трех видов: , , , где , , , .
Пример 8.3.2.
Грамматика
является грамматикой в нормальной форме Хомского.
Теорема 8.3.3.
Каждая контекстно-свободная грамматика эквивалентна некоторой грамматике в нормальной форме Хомского.
Доказательство. Пусть дана контекстно-свободная грамматика . Проведем ряд преобразований этой грамматики так, что порождаемый ею язык остается неизменным.
Если правая часть какого-нибудь правила содержит символ S, то заменим грамматику
на грамматику
где S0 - новый символ, не принадлежащий множеству .
Заменим во всех правилах каждый терминальный символ a на новый нетерминальный символ Ta
и добавим к множеству P правила
для всех .
Устраним правила вида , где , заменив каждое из них на ряд более коротких правил (при этом добавляются новые нетерминальные символы).
Теперь устраним все правила вида , где A не является начальным символом. Это можно сделать так же, как в доказательстве теоремы 8.2.1.
Если для каких-то ,
и
множество P содержит правила
и , но не содержит правила , то добавим это правило в P. Повторяем эту процедуру, пока возможно. После этого исключим из множества P все правила вида .
Пример 8.3.4.
Грамматика
эквивалентна следующей грамматике в нормальной форме Хомского:
Теорема 8.3.5.
Если контекстно-свободный язык не содержит пустого слова, то он порождается некоторой грамматикой, в которой каждое правило имеет один из следующих двух видов: , , где , , , .
Упражнение 8.3.6. Найти контекстно-свободную грамматику в нормальной форме Хомского, эквивалентную грамматике
