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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Преобразование грамматики в нормальную форму Хомского)
Строка 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 \varepsilon </tex>, то <tex> A </tex> {{---}} обнуляемый.
 
−
 
−
Если <tex> A \rightarrow B_1....B_n </tex>, где все <tex> B_i </tex> обнуляемые, то <tex> A </tex> тоже обнуляемый.
 
 
}}
 
}}
  
Строка 25: Строка 18:
  
 
Если <tex> (A, B) </tex> {{---}} узловая пара, а <tex> B \rightarrow C </tex>, то <tex> (A, C) </tex> тоже узловая пара.
 
Если <tex> (A, B) </tex> {{---}} узловая пара, а <tex> B \rightarrow C </tex>, то <tex> (A, C) </tex> тоже узловая пара.
−
}}
 
−
 
−
{{Определение
 
−
|definition=Правило <tex> A \rightarrow w </tex> называется '''смешанным''', если <tex> w </tex> содержит хотя бы один терминал и хотя бы один нетерминал. 
 
 
}}
 
}}
  
Строка 36: Строка 25:
 
|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> S_0 </tex> с новым правилом <tex> S_0 \rightarrow S </tex>, где <tex> S </tex> {{---}} старая стартовая вершина. Добавим в <tex> \Gamma_1 </tex> новую вершину, правило и <tex> \Gamma </tex>.
 
 
# Удаление <tex> \varepsilon </tex>-правил.
 
# Удаление <tex> \varepsilon </tex>-правил.
−
##Если <tex> A \rightarrow \varepsilon </tex>, то выкинем такое правило.
+
##Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим <tex> \Gamma_1 </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> w </tex> в следующем виде <tex> w=w_0 N_0 w_1 N_1 ... w_{n-1} N_{n-1} w_n N_n </tex>, где <tex> N_i </tex> {{---}} вхождение обнуляемого нетерминала, а <tex> w_i </tex> не содержит обнуляемых нетерминалов. Добавим в <tex> \Gamma_2 </tex> все правила, которые можно получить удалением всевозможных комбинаций <tex> N_i </tex> из <tex> w </tex>. Таких вариантов будет <tex> 2^n </tex>.
 
−
#:Если стартовая вершина <tex> \Gamma_1 </tex> является обнуляемой, то добавим в <tex> \Gamma_2 </tex> правило <tex> S_0 \rightarrow \varepsilon </tex>.
 
 
# Преобразование узловых пар.
 
# Преобразование узловых пар.
−
#:Для каждой узловой пары <tex> (A, B) </tex>, найдем все правила <tex> B \rightarrow w </tex>, где <tex> w </tex> {{---}} произвольная строка терминалов и нетерминалов,  и добавим <tex> A \rightarrow w </tex> в <tex> \Gamma_3 </tex>.
+
#:Для каждой узловой пары <tex> (A, B) </tex>, найдем все правила <tex> B \rightarrow w </tex>, где <tex> w </tex> {{---}} произвольная строка терминалов и нетерминалов,  и добавим <tex> A \rightarrow w </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_4 </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_4 </tex>.  
 
 
# Преобразование длинных правил.
 
# Преобразование длинных правил.
−
#:Для каждого правила вида <tex> A \rightarrow B_0 B_1 ... B_n </tex>, где <tex> n \ge 2 </tex>, добавим новые нетерминалы <tex> A_1, A_2, ... , A_{n-2} </tex> и правила <tex> A \rightarrow B_1 A_1 </tex>, <tex> A_1 \rightarrow B_2 A_2 </tex>, <tex> A_2 \rightarrow B_3 A_3 </tex>, <tex> ... </tex> , <tex> A_{n-2} \rightarrow B_{n-1} B_n </tex> в <tex> \Gamma_5 </tex>.  
+
#:Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим <tex> \Gamma_3 </tex>.
  
−
Таким образом мы получили грамматику <tex> \Gamma_5 </tex> в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.  
+
Таким образом мы получили грамматику <tex> \Gamma_3 </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

Версия 05:53, 4 ноября 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 [/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]\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] (A, B) [/math], найдем все правила [math] B \rightarrow w [/math], где [math] w [/math] — произвольная строка терминалов и нетерминалов, и добавим [math] A \rightarrow w [/math] в [math] \Gamma_2 [/math].
  3. Преобразование длинных правил.
    Воспользуемся алгоритмом удаления длинных правил из грамматики. Получим [math] \Gamma_3 [/math].
Таким образом мы получили грамматику [math] \Gamma_3 [/math] в нормальной форме Хомского, которая допускает тот же язык, что и [math] \Gamma [/math].
[math]\triangleleft[/math]

Литература

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