Изменения

Приведем алгоритм, позволяющий для к.с. грамматики '''без &epsilon;<tex> \varepsilon </tex>-правил''' построить эквивалентную ей к.с. грамматику (без &epsilon;<tex> \varepsilon </tex>-правил), не содержащую левой рекурсии.

#Воспользоваться [[Удаление_eps-правил_из_грамматики | алгоритмом удаления &epsilon;<tex> \varepsilon </tex>-правил]]. Получим грамматику без &epsilon;<tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>

<ol><li>Запишем все правила вывода из <tex>A</tex> в виде<tex>A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где<ul><li> <tex>\alpha</tex> - непустая последовательность терминалов и нетерминалов (<tex>\alpha \ne \epsilon </tex>)</li><li> <tex>\beta</tex> - непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li></ul><li>Заменим правила вывода из <tex>A</tex> на: <tex>A \rightarrow \beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex> </li>

<tex>A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex> где* <tex>\alpha</tex> - непустая последовательность терминалов и нетерминалов (<tex>\alpha \ne \epsilon </tex>)* <tex>\beta</tex> - непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</texli>. Заменим правила вывода из <tex>A</tex> на: <tex>A \rightarrow \beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex> И создадим новый нетерминал <tex>A^\prime \rightarrow \alpha_1A^\prime\, |\, \ldots\, |\, \alpha_nA^\prime | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex> </li></li></ol>