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

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

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

Пусть [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]