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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Определение:
Грамматикой в нормальной форме Хомского (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 w [/math] называется смешанным, если [math] w [/math] содержит хотя бы один терминал и хотя бы один нетерминал.


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

Теорема:
Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского.
Доказательство:
[math]\triangleright[/math]

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

  1. Удаление [math] \varepsilon [/math]-правил.
    1. Воспользуемся алгоритмом удаления [math] \varepsilon [/math]-правил из грамматики. Получим [math] \Gamma_1 [/math].
  2. Удаление цепных правил.
    Воспользуемся алгоритмом удаления цепных правил из грамматики. Получим [math] \Gamma_2 [/math].
  3. Преобразование смешанных правил.
    Если [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_3 [/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_3 [/math].
  4. Преобразование длинных правил.
    Воспользуемся алгоритмом удаления длинных правил из грамматики. Получим [math] \Gamma_4 [/math].
Таким образом мы получили грамматику [math] \Gamma_4 [/math] в нормальной форме Хомского, которая допускает тот же язык, что и [math] \Gamma [/math].
[math]\triangleleft[/math]

Литература