Изменения

#:Для всех правил вида <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> n \ge 3 </tex> могло появиться <tex> n-1 </tex> новых правил. При удалении <tex> \varepsilon </tex>-правил из грамматики, содержащей правила длины 0, 1 и 2, размеры грамматики могли вырасти не больше, чем в 4 3 раза. Всего цепных правил в грамматике не больше, чем <tex> n^2 </tex>, где <tex> n </tex> {{---}} число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар (их не больше <tex> n^2 </tex>) и производим добавление нецепных правил. Если максимальное количество нецепных правил среди всех возможных пар равно <tex> k </tex>, то добавить мы сможем не больше, чем <tex> k*n^2 </tex>. Проанализируем ситуации, когда в правиле несколько терминалов: при таком порядке действий их однозначно два. Для каждого из таких правил мы добавляем еще по два нетерминала и правила.