271
правка
Изменения
→Преобразование грамматики в нормальную форму Хомского
# Преобразование смешанных правил.
#:Если <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> A_{n-2} \rightarrow B_{n-1} B_n </tex> в <tex> \Gamma_5 </tex>.
