Изменения

[[Файл:derivation_tree_T.png|240px|thumb|left|Дерево вывода <tex>T</tex>]]Будем называть <tex>v_i</tex> левой ветвящейся вершиной, если ее сын, не принадлежащий пути <tex>v_1, v_2, ..., v_p</tex>, имеет выделенного потомка лежащего слева от <tex>v_p</tex>. В противном случае назовем <tex>v_i</tex> правой ветвящейся вершиной. Рассмотрим последние <tex>2m + 3</tex> вершины принадлежащий пути <tex>v_1, v_2, ..., v_p</tex>. Предположим, что хотя бы <tex>m + 2</tex> вкршины левые ветвящиеся (случай, когда хотя бы <tex>m + 2</tex> вершины правые ветвящиеся, разбирается аналогично). Пусть <tex>u_1, u_2, ..., u_{m + 2}</tex> — последние <tex>m + 2</tex> левые ветвящиеся вершины. Поскольку <tex>m = |N|</tex>, то среди них можно найти как минимум две вершины, соответствующие одному нетерменалу. Обозначим эти вершины <tex>a</tex> и <tex>b</tex>, причем <tex>b</tex> потомок <tex>a</tex>. Тогда на рисунке показано как представить <tex>\omega</tex> в требуемом виде.