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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Приведение грамматики к нормальной форме Хомского)
Строка 23: Строка 23:
 
# Удаление цепных правил.
 
# Удаление цепных правил.
 
#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную <tex> \Gamma_1 </tex>.
 
#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную <tex> \Gamma_1 </tex>.
# Удалим бесполезные символы.
+
# Удалим не слишком полезные символы.
 
#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_2 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться.
 
#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_2 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться.
 
# Уберем ситуации, когда в правиле встречаются несколько терминалов.
 
# Уберем ситуации, когда в правиле встречаются несколько терминалов.

Версия 02:18, 19 декабря 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]\triangleright[/math]

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

  1. Удаление [math] \varepsilon [/math]-правил.
    Воспользуемся алгоритмом удаления [math] \varepsilon [/math]-правил из грамматики. Получим грамматику [math] \Gamma_1 [/math], эквивалентную исходной, но в которой нет [math]\varepsilon [/math]-правил.
  2. Удаление цепных правил.
    Воспользуемся алгоритмом удаления цепных правил из грамматики. Алгоритм работает таким образом, что новые [math] \varepsilon [/math]-правила не образуются. Получим грамматику [math] \Gamma_2 [/math], эквивалентную [math] \Gamma_1 [/math].
  3. Удалим не слишком полезные символы.
    Воспользуемся алгоритмом удаления бесполезных символов из грамматики. Так как [math] \Gamma_2 [/math] эквивалентна [math] \Gamma [/math], то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые [math]\varepsilon[/math]-правила и цепные правила не могли появиться.
  4. Уберем ситуации, когда в правиле встречаются несколько терминалов.
    Для всех правил вида [math] A \rightarrow u_1 u_2 ... u_n [/math] (где [math] n \ge 2 [/math], [math] u_i [/math] — терминал или нетерминал) заменим все терминалы [math] u_i [/math] на переменные [math] U_i [/math] и добавим правила [math] U_i \rightarrow u_i [/math]. Теперь правила содержат либо одиночный терминал, либо строку из нетерминалов.
  5. Уберем длинные правила.
    Воспользуемся алгоритмом удаления длинных правил из грамматики.
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и [math] \Gamma [/math].
[math]\triangleleft[/math]

Литература