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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 10: Строка 10:
  
 
где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил.
 
где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил.
−
}}
 
−
 
−
{{Определение
 
−
|definition=Правило <tex> A \rightarrow w </tex> называется '''смешанным''', если <tex> w </tex> содержит хотя бы один терминал и хотя бы один нетерминал. 
 
 
}}
 
}}
  
Строка 21: Строка 17:
 
|statement=Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского.
 
|statement=Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского.
 
|proof=
 
|proof=
−
Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее к нормальной форме Хомского необходимо выполнить четыре шага. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>.
+
Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее к нормальной форме Хомского необходимо выполнить пять шагов. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>.
  
 
# Удаление <tex> \varepsilon </tex>-правил.
 
# Удаление <tex> \varepsilon </tex>-правил.
−
#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим <tex> \Gamma_1 </tex>.
+
#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики.
 
# Удаление цепных правил.
 
# Удаление цепных правил.
−
#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Получим <tex> \Gamma_2 </tex>.
+
#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики.
−
# Преобразование смешанных правил.
+
# Удалим бесполезные символы.
−
#:Если <tex> A \rightarrow w </tex> {{---}} смешанное правило, то можно представить <tex> w </tex> в виде <tex> w=v_0 c_1 v_1 c_2 ... v_{n-1} c_n v_n </tex>, где <tex> v_i </tex> {{---}} строка нетерминалов, а <tex> c_i </tex> является терминалом. Тогда для каждого <tex> c_i </tex> добавим нетерминал <tex> C_i </tex> и правило <tex> C_i \rightarrow c_i </tex> в <tex> \Gamma_3 </tex>. Получим <tex> w'=v_0 C_1 v_1 C_2 ... v_{n-1} C_n v_n </tex>. Добавим правило <tex> A \rightarrow w' </tex> в <tex> \Gamma_3 </tex>.  
+
#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики.
−
# Преобразование длинных правил.
+
# Уберем ситуации, когда в правиле встречаются несколько терминалов.
−
#:Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим <tex> \Gamma_4 </tex>.
+
#:Для всех правил вида <tex> A \rightarrow u_1 u_2 ... u_n </tex> (где <tex> n \ge 2 </tex>, <tex> u_i </tex> {{---}} терминал или нетерминал) заменим все терминалы <tex> u_i </tex> на переменные <tex> U_i </tex> и добавим правила <tex> U_i \rightarrow u_i </tex>. Теперь правила содержат либо одиночный терминал, либо строку из нетерминалов.  
−
 
+
# Уберем длинные правила.
−
Таким образом мы получили грамматику <tex> \Gamma_4 </tex> в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.  
+
#: Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики.
 +
Таким образом мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.  
 
}}
 
}}
  
 
==Литература==
 
==Литература==
 
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf
 
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf

Версия 04:13, 7 ноября 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]-правил из грамматики.
  2. Удаление цепных правил.
    Воспользуемся алгоритмом удаления цепных правил из грамматики.
  3. Удалим бесполезные символы.
    Воспользуемся алгоритмом удаления бесполезных символов из грамматики.
  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]

Литература

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Нормальная_форма_Хомского&oldid=12819»