271
правка
Изменения
Нет описания правки
Если <tex> (A, B) </tex> {{---}} узловая пара, а <tex> B \rightarrow C </tex>, то <tex> (A, C) </tex> тоже узловая пара.
}}
{{Определение
|definition=Правило <tex> A \rightarrow w </tex> называется '''смешанным''', если <tex> w </tex> содержит хотя бы один терминал и хотя бы один нетерминал.
}}
|statement=Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского.
|proof=
Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее к нормальной форме Хомского необходимо выполнить три четыре шага. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>.
# Удаление <tex> \varepsilon </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_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_3 Gamma_4 </tex>.
Таким образом мы получили грамматику <tex> \Gamma_3 Gamma_4 </tex> в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.
}}
==Литература==
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf
