Изменения

#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_3 </tex>, эквивалентную <tex> \Gamma_1 Gamma </tex>.

#:Для всех правил вида <tex> A \rightarrow u_1 u_2</tex> (где <tex> u_i </tex> {{---}} терминал или нетерминал) заменим все терминалы <tex> u_i </tex> на переменные новые нетерминалы <tex> U_i </tex> и добавим правила <tex> U_i \rightarrow u_i </tex>. Теперь правила содержат либо одиночный терминал, либо строку из двух нетерминалов.

 Заметим, что размеры грамматики при таком порядке действий возрастают полиномиально.  При удалении длинных правил из каждого правила длины <tex> n k \ge 3 </tex> могло появиться <tex> nk-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>. Проанализируем ситуации Наконец, на последнем шаге может произойти добавление не более, когда в правиле несколько терминалов: при таком порядке действий их однозначно два. Для каждого из таких чем <tex>|\Sigma|</tex> (<tex>\Sigma</tex> {{---}} алфавит грамматики) новых правил мы добавляем еще по два нетерминала и правила, причем все они будут длины 1.