Математическая теория формальных языков

       

Нормальная форма Хомского


Определение 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. Найти контекстно-свободную грамматику в нормальной форме Хомского, эквивалентную грамматике



Содержание раздела