Изменения
Нет описания правки
#:Для всех правил вида <tex> A \rightarrow u_1 u_2 ... u_n </tex> (где <tex> n \ge 2 </tex>, <tex> u_i </tex> {{---}} терминал или нетерминал) заменим все терминалы <tex> u_i </tex> на переменные <tex> U_i </tex> и добавим правила <tex> U_i \rightarrow u_i </tex>. Теперь правила содержат либо одиночный терминал, либо строку из нетерминалов.
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.
Заметим, что размеры грамматики при таком порядке действий возрастают полиномиально. При удалении длинных правил из каждого правила длины <tex> n \ge 3 </tex> могло появиться <tex> n-1 </tex> новых правил. При удалении <tex> \varepsilon </tex>-правил из грамматики, содержащей правила длины 0, 1 и 2, размеры грамматики могли вырасти не больше, чем в 4 раза. Всего цепных правил в грамматике не больше, чем <tex> n^2 </tex>, где <tex> n </tex> {{---}} число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар (их не больше <tex> n^2 </tex>) и производим добавление нецепных правил. Если максимальное количество нецепных правил среди всех возможных пар равно <tex> k </tex>, то добавить мы сможем не больше, чем <tex> k*n^2 </tex>. Если Проанализируем ситуации, когда в правиле несколько терминалов, то : при таком порядке действий их однозначно два. Для каждого из таких правил мы добавляем еще по два нетерминала и правила.
}}
==Литература==
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf
