Изменения

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