Изменения

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

##Если <tex> A \rightarrow \varepsilon </tex>, то выкинем такое правило.##Если <tex> A \rightarrow w </tex>, где <tex> w </tex> не содержит Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <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 \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 Gamma_2 </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 Gamma_3 </tex>.

Таким образом мы получили грамматику <tex> \Gamma_5 Gamma_3 </tex> в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.