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

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

Правила вида [math]A \to B[/math] ([math]A,B[/math] - нетерминалы) называются цепными.

Зачастую удобно рассматривать грамматики без цепных правил. Оказывается, что верно следующее утверждение:

Утверждение:

Для любой контекстно-свободной (К-С) грамматики существует эквивалентная ей К-С грамматика без цепных правил.

[math]\triangleright[/math]

Построим граф. Вершинами в нем будут нетерминальные символы, а ребро из [math]A[/math] в [math]B[/math] будет тогда и только тогда, когда есть правило [math]A \to B[/math]. Сделаем транзитивное замыкание для этого графа и добавим правила, соответствующие новым ребрам. Заметим, что теперь любое выводимое слово можно вывести, используя не более одного цепного правила подряд. Также нетрудно понять, что новая грамматика эквивалентна старой. Далее, рассмотрим все цепные правила [math]A \to B[/math]. Пусть из [math]B[/math] можно вывести: [math]B \to \alpha_1 \mid \alpha_2 \mid \dots \mid \alpha_n[/math]. Тогда добавим следующее правило в нашу грамматику: [math]A \to \alpha_1 \mid \alpha_2 \mid \dots \mid \alpha_n[/math]. При этом получившаяся грамматика будет тоже эквивалентна исходной. Заметим, что теперь любое слово можно вывести, не используя цепных правил вовсе. Поэтому удалим их. Итого, была построена К-С грамматика без цепных правил, эквивалентная исходной.

[math]\triangleleft[/math]