54
правки
Изменения
замена знаков неравенств
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>.
Упорядочим нетерминалы и будем добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \le leqslant i</tex>.
Если данное условие выполняется для всех<tex>A_i</tex>, то в грамматике нет <tex>A_i \to^* A_i</tex>, а значит не будет левой рекурсии.
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq leqslant j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.
После <tex>i</tex> итерации внешнего цикла в любой продукции внешнего цикла в любой продукции вида <tex>A_k \to A_l\alpha, k < i</tex>, должно быть <tex>l > k</tex>. В результате при следующей итерации внутреннего цикла растет нижний предел <tex>m</tex> всех продукций вида <tex>A_i \to A_m\alpha</tex> до тех пор, пока не будет достигнуто <tex>i \le leqslant m </tex>.
После <tex>i</tex> итерации внешнего цикла в грамматике будут только правила вида <tex>A_i \to A_j\alpha</tex>, где <tex>j > i</tex>.
<tex>A_1 \to 0 | 1</tex>
<tex>A_{i+1} \to {A_i}0 | {A_i}1 </tex> для <tex>1 \leq leqslant i < n</tex>
Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным. Если упорядочить нетерминалы по убыванию в грамматике изменений не будет.
