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

Несколько определений

Определение:

Грамматикой в нормальной форме Хомского (Chomsky normal form) называется грамматика, в которой могут содержатся правила только следующего вида [math]A \rightarrow B C [/math]. [math]A \rightarrow a [/math]. [math]S \rightarrow \varepsilon [/math]. (где [math] a [/math] — терминал, [math] A, B, C [/math] — нетерминалы, [math] S [/math] — стартовая вершина, [math] \varepsilon [/math] — пустая строка, стартовая вершина не содержится в правых частях правил).

Определение:

Нетерминал называется обнуляемым, если из него можно прямо или косвенно получить пустую строку. Если [math] A \rightarrow \varepsilon [/math], то [math] A [/math] — обнуляемый. Если [math] A \rightarrow B_1....B_n [/math], где все [math] B_i [/math] обнуляемые, то [math] A [/math] тоже обнуляемый.

Определение:

Пара нетерминалов [math] A [/math] и [math] B [/math] называется узловой, если [math] A \Rightarrow^* B [/math]. [math] \forall A [/math] выполняется [math] (A, A) [/math] — узловая пара. Если [math] (A, B) [/math] — узловая пара, а [math] B \rightarrow C [/math], то [math] (A, C) [/math] тоже узловая пара.

Определение:

Правило [math] A \rightarrow w [/math] называется смешанным, если [math] w [/math] содержит хотя бы один терминал и хотя бы один нетерминал.

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

Рассмотрим контекстно-свободную грамматику [math] \Gamma [/math]. Для преобразования ее в нормальную форму Хомского необходимо выполнить 5 шагов. На каждом шаге мы строим новую [math] \Gamma_i [/math], которая допускает тот же язык, что и [math] \Gamma [/math].

1. Создание новой стартовой вершины.

   Создадим новую стартовую вершину [math] S_0 [/math] с новым правилом [math] S_0 \rightarrow S [/math], где [math] S [/math] — старая стартовая вершина. Добавим в [math] \Gamma_1 [/math] эту вершину, правило и [math] \Gamma [/math].

2. Удаление [math] \varepsilon [/math]-правил.
   1. Если [math] A \rightarrow \varepsilon [/math], то выкинем такое правило.
   2. Если [math] A \rightarrow w [/math], где [math] w [/math] не содержит [math] \varepsilon [/math] и обнуляемых нетерминалов, то добавим такое правило в [math] \Gamma_2 [/math].
   3. Если [math] A \rightarrow w [/math], причем [math] w [/math] содержит обнуляемые нетерминалы, то представим [math] w [/math] в следующем виде [math] w=w_0 N_0 w_1 N_1 ... w_{n-1} N_{n-1} w_n N_n [/math], где [math] N_i [/math] — вхождение обнуляемого нетерминала, [math] w_i [/math] не содержит обнуляемых нетерминалов. Добавим в [math] \Gamma_2 [/math] все правила, которые можно получить удалением всевозможных комбинаций [math] N_i [/math] из [math] w [/math]. Таких вариантов будет [math] 2^n [/math].

   Если стартовая вершина [math] \Gamma_1 [/math] является обнуляемой, то добавим в [math] \Gamma_2 [/math] правило [math] S_0 \rightarrow \varepsilon [/math].

3. Преобразование узловых пар.

   Для каждой узловой пары [math] (A, B) [/math], найдем все правила [math] B \rightarrow w [/math], где [math] w [/math] — произвольная строка терминалов и нетерминалов, и добавим [math] A \rightarrow w [/math] в [math] \Gamma_3 [/math].

4. Преобразование смешанных правил.

   Если [math] A \rightarrow w [/math] — смешанное правило, то можно представить [math] w [/math] в виде [math] w=v_0 c_1 v_1 c_2 ... v_{n-1} c_n v_n [/math], где [math] v_i [/math] — строка нетерминалов, а [math] c_i [/math] является терминалом. Тогда для каждого [math] c_i [/math] добавим нетерминал [math] C_i [/math] и правило [math] C_i \rightarrow c_i [/math] в [math] \Gamma_4 [/math]. Получим [math] w'=v_0 C_1 v_1 C_2 ... v{n-1} C_n v_n [/math]. Добавим правило [math] A \rightarrow w' [/math] в [math] \Gamma_4 [/math].

5. Преобразование длинных правил.

   Для каждого правила вида [math] A \rightarrow B_0 B_1 ... B_n [/math], где [math] n \ge 2 [/math], добавим новые нетерминалы [math] A_1, A_2, ... , A_{n-2} [/math] и правила [math] A \rightarrow B_1 A_1 [/math], [math] A_1 \rightarrow B_2 A_2 [/math], [math] A_2 \rightarrow B_3 A_3 [/math], [math] ... [/math] , [math] A_{n-2} \rightarrow B_{n-1} B_n [/math] в [math] \Gamma_5 [/math].

После пятого шага грамматика [math] \Gamma_5 [/math] содержит только правила вида [math] A \rightarrow B C [/math] и [math] A \rightarrow a [/math], где [math] A, B, C [/math] — нетерминалы, [math] a [/math] — терминал. Возможно, что также присутствует правило [math] S_0 \rightarrow \varepsilon [/math]. Новая грамматика допускает тот же язык, что и [math] \Gamma [/math].

Заметим, что любую контекстно-свободную грамматику можно привести к нормальной форме Хомского. Такая форма очень удобна для работы многих алгоритмов над грамматиками, например, алгоритм Кока-Янгера-Касами.

Литература

• http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf