Изменения

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить  {{Определение|definition=Говорят, что нетерминал <tex>X</tex> {{---}} '''прямой левый вывод''' (англ. ''direct left corner'') из <tex>A</tex>, если существует правило вида <tex>A \to X\alpha</tex>.}} {{Определение|definition='''Левый вывод''' (англ. ''left corner'') {{---}} транзитивное, рефлексивное замыкание отношения "быть прямым левым выводом".}} Во внутреннем цикле алгоритма для всех нетерминалов <tex>A_i</tex> и <tex>A_j</tex>, таких что <tex>j < i</tex> и <tex>A_j</tex> - прямой левый вывод из <tex>A_i</tex> заменяем все прямые левые выводы <tex>A_j</tex> из <tex>A_i</tex> на все выводы из <tex>A_j</tex>. Это действие удаляет левую рекурсию только если <tex>A_i</tex> - леворекурсивный нетерминал и <tex>A_j</tex> содержится в выводе <tex>A_i</tex> (то есть <tex>A_i</tex> - левый вывод из <tex>A_j</tex>,в то время как <tex>A_j</tex> - левый вывод из <tex>A_i</tex>). Перестанем добавлять бесполезные выводы, которые не участвуют в удалении левой рекурсии, упорядочив нетерминалы так: если <tex>j < i</tex> и <tex>A_j</tex> - прямой левый вывод из <tex>A_i</tex>, то <tex>A_i</tex> - левый вывод из <tex>A_j</tex>.Упорядочим их по убыванию уменьшению количества различных прямых левых выводов из них. Так как отношение "быть левым выводом" транзитивно,то если <tex>C</tex> - прямой левый вывод из <tex>B</tex>, то каждый левый вывод из С также будет левым выводом из <tex>B</tex>. А так как отношение "быть левым выводом" рефлексивно, <tex>B</tex> явлеяется своим левым выводом, а значит если <tex>C</tex> - прямой левый вывод из <tex>B</tex> - он должен следовать за <tex>B</tex> в грамматике изменений упорядоченном множестве, если только <tex>B</tex> не будетявляется левым выводом из <tex>C</tex>.