271
правка
Изменения
→Преобразование грамматики в нормальную форму Хомского
# Удаление <tex> \varepsilon </tex>-правил.
##Если <tex> A \rightarrow \varepsilon </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>.
# Преобразование правил с длинной правой частью.
