Удаление длинных правил из грамматики

Задача удаления длинных правил из грамматики возникает при попытке ее приведения к нормальной форме Хомского.

Определение:

Пусть [math]\Gamma[/math] — контекстно-свободная грамматика. Правило [math]A \rightarrow \beta [/math] называется длинным если [math]|\beta| \gt 2[/math]

Постановка задачи

Пусть [math]\Gamma[/math] — контекстно-свободная грамматика, содержащая длинные правила. Требуется построить эквивалентную грамматику [math]\Gamma'[/math], не содержащую длинных правил.

Алгоритм

Расмотрим длинное правило [math]A \rightarrow a_1 a_2 \ldots a_k[/math], [math]k \gt 2[/math], [math]a_i \in \Sigma \cup N[/math]
Добавим в грамматику [math]k - 2[/math] новых нетерминалов [math]B_1, B_2, \ldots B_{k-2}[/math]
Добавим в грамматику [math]k-1[/math] новое правило:
[math]A \rightarrow a_1B_1[/math]
[math]B_1 \rightarrow a_2B_2[/math]
[math]B_2 \rightarrow a_3B_3[/math]
[math]\ldots [/math]
[math]B_{k-2} \rightarrow a_{k-1}a_{k}[/math]
Удалим из грамматики правило [math]A \rightarrow a_1 a_2 \ldots a_k[/math]. Проделаем описанную операцию с каждым длинным правилом в [math]\Gamma[/math]

Пример работы

Покажем, как описанный алгоритм будет работать на следующей грамматике:
[math]S \rightarrow AB[/math]
[math]A \rightarrow aBcB[/math]
[math]B \rightarrow def[/math]

Для правила [math]A \rightarrow aBcB[/math] вводим 2 новых нетерминала [math]A_1, A_2[/math], и 3 новых правила:
[math]A \rightarrow aA_1[/math]
[math]A_1 \rightarrow BA_2[/math]
[math]A_2 \rightarrow bB[/math]

Для правила [math]B \rightarrow def[/math] вводим 1 новыq нетерминал [math]B_1[/math], и 2 новых правила:
[math]B \rightarrow dB_1[/math]
[math]B_1 \rightarrow ef[/math]

В итоге, полученная грамматика [math]\Gamma'[/math] будет иметь вид:
[math]S \rightarrow AB[/math]
[math]A \rightarrow aA_1[/math]
[math]A_1 \rightarrow BA_2[/math]
[math]A_2 \rightarrow bB[/math]
[math]B \rightarrow dB_1[/math]
[math]B_1 \rightarrow ef[/math]