Изменения

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

#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим <tex> \Gamma_1 </tex>.

#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Получим <tex> \Gamma_2 </tex># Удалим бесполезные символы.#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики.# Преобразование смешанных правилУберем ситуации, когда в правиле встречаются несколько терминалов. #:Если Для всех правил вида <tex> A \rightarrow w u_1 u_2 ... u_n </tex> {{---}} смешанное правило, то можно представить <tex> w (где </tex> в виде <tex> w=v_0 c_1 v_1 c_2 ... v_{n-1} c_n v_n \ge 2 </tex>, где <tex> v_i u_i </tex> {{---}} строка нетерминалов, а терминал или нетерминал) заменим все терминалы <tex> c_i u_i </tex> является терминалом. Тогда для каждого на переменные <tex> c_i U_i </tex> и добавим нетерминал <tex> C_i правила </tex> и правило <tex> C_i U_i \rightarrow c_i </tex> в <tex> \Gamma_3 u_i </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> \Gamma_4 </tex> в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.