271
правка
Изменения
→Преобразование грамматики в нормальную форму Хомского
==Преобразование грамматики в нормальную форму Хомского==
Рассмотрим [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободную грамматику]] <tex> \Gamma </tex>. Для преобразования ее в нормальную форму Хомского необходимо избавиться от правил следующего типавыполнить 5 шагов. Каждый шаг работает у преобразованной грамматикой.
# Создание новой стартовой вершины.
##Если <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>.
# Удаление вершин, которые могут породить друг другаПреобразование узловых пар.##
# Преобразование правил с длинной правой частью.
