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

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

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

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

Постановка задачи. Пусть задана контекстно-свободная грамматика [math]\Gamma[/math]. И пусть существует правило вида:

• [math]A \rightarrow \alpha_1 \alpha_2 ... \alpha_k [/math].

Требуется получить лишь правила вида:

• [math]A \rightarrow BC[/math]

Удаление длинных правил. Давайте формально перезапишем:

• [math]A \rightarrow \alpha_1 A_1 [/math]. Тогда:
• [math]A_1 \rightarrow \alpha_2 A_2[/math]. И т.д.

На [math]k-1 -[/math]ой итерации получим:

• [math]A_{k-1} \rightarrow \alpha_k [/math]

Тогда финально получим:

• [math]A \rightarrow A_{k-2} A_{k-1} [/math].