Нормальная форма Хомского — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Преобразование грамматики в нормальную форму Хомского)
(Преобразование грамматики в нормальную форму Хомского)
Строка 33: Строка 33:
 
# Создание новой стартовой вершины.
 
# Создание новой стартовой вершины.
 
#: Создадим новую стартовую вершину <tex> S_0 </tex> с новым правилом <tex> S_0 \rightarrow S </tex>, где <tex> S </tex> {{---}} старая стартовая вершина. Получим <tex> \Gamma_1 </tex>.
 
#: Создадим новую стартовую вершину <tex> S_0 </tex> с новым правилом <tex> S_0 \rightarrow S </tex>, где <tex> S </tex> {{---}} старая стартовая вершина. Получим <tex> \Gamma_1 </tex>.
# Удаление <tex> \varepsilon- </tex> правил.
+
# Удаление <tex> \varepsilon </tex>-правил.
 
##Если <tex> A \rightarrow \varepsilon </tex>, то выкинем такое правило.
 
##Если <tex> A \rightarrow \varepsilon </tex>, то выкинем такое правило.
 
##Если <tex> A \rightarrow w </tex>, где <tex> w </tex> не содержит <tex> \varepsilon </tex> и обнуляемых переменных, то добавим такое правило в <tex> \Gamma_2 </tex>.
 
##Если <tex> A \rightarrow w </tex>, где <tex> w </tex> не содержит <tex> \varepsilon </tex> и обнуляемых переменных, то добавим такое правило в <tex> \Gamma_2 </tex>.

Версия 06:57, 26 октября 2011

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

Определение:
Грамматикой в нормальной форме Хомского (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] \Gamma [/math]. Для преобразования ее в нормальную форму Хомского необходимо избавиться от правил следующего типа.

  1. Создание новой стартовой вершины.
    Создадим новую стартовую вершину [math] S_0 [/math] с новым правилом [math] S_0 \rightarrow S [/math], где [math] S [/math] — старая стартовая вершина. Получим [math] \Gamma_1 [/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. Удаление вершин, которые могут породить друг друга.
  4. Преобразование правил с длинной правой частью.


Рассмотрим контекстно-свободную грамматику [math]\Gamma[/math], из которой удалены бесполезные символы, [math]\varepsilon[/math]-правила, длинные правила и цепные правила. Такая грамматика содержит только правила следующего вида:

  • [math]A \rightarrow BC[/math]
  • [math]A \rightarrow Bc[/math]
  • [math]A \rightarrow bC[/math]
  • [math]A \rightarrow bc[/math]
  • [math]A \rightarrow a[/math]
  • возможно, [math]S \rightarrow \varepsilon[/math] (при условии, что [math]S[/math] не содержится в правых частях правил)

Избавимся от правил, в правых частях которых записаны два символа, один из которых является терминалом, то есть правил вида [math]A \rightarrow Bc[/math], [math]A \rightarrow bC[/math] и [math]A \rightarrow bc[/math]. Введем для каждого терминала [math]a[/math] "персональный" нетерминал [math]N_a[/math]. Затем правила вида [math]A \rightarrow Bc[/math] заменим парой правил [math]A \rightarrow BN_c[/math] и [math]N_c \rightarrow c[/math], правила вида [math]A \rightarrow bC[/math] заменим парой правил [math]A \rightarrow N_bC[/math] и [math]N_b \rightarrow b[/math], а правила вида [math]A \rightarrow bc[/math] — тройкой правил [math]A \rightarrow N_bN_c[/math], [math]N_b \rightarrow b[/math] и [math]N_c \rightarrow c[/math].

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

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