69
правок
Изменения
Нет описания правки
<tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex> <br>
Удалим из грамматики правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>. Проделаем описанную операцию с каждым длинным правилом в <tex>\Gamma</tex>
== Пример работы ==
Покажем, как описанный алгоритм будет работать на следующей грамматике: <br>
<tex>S \rightarrow AB</tex> <br>
<tex>A \rightarrow aBcB</tex> <br>
<tex>B \rightarrow def</tex> <br>
Для правила <tex>A \rightarrow aBcB</tex> вводим 2 новых нетерминала <tex>A_1, A_2</tex>, и 3 новых правила: <br>
<tex>A \rightarrow aA_1</tex> <br>
<tex>A_1 \rightarrow BA_2</tex> <br>
<tex>A_2 \rightarrow bB</tex> <br>
Для правила <tex>B \rightarrow def</tex> вводим 1 новыq нетерминал <tex>B_1</tex>, и 2 новых правила: <br>
<tex>B \rightarrow dB_1</tex> <br>
<tex>B_1 \rightarrow ef</tex> <br>
В итоге, полученная грамматика <tex>\Gamma'</tex> будет иметь вид: <br>
<tex>S \rightarrow AB</tex> <br>
<tex>A \rightarrow aA_1</tex> <br>
<tex>A_1 \rightarrow BA_2</tex> <br>
<tex>A_2 \rightarrow bB</tex> <br>
<tex>B \rightarrow dB_1</tex> <br>
<tex>B_1 \rightarrow ef</tex> <br>
