Изменения

|definition = Правила Цепное правило — правило вида <tex>A \to rightarrow B</tex> (, где <tex>A,</tex> и <tex>B</tex> - — нетерминалы) называются цепными.

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

{{УтверждениеОпределение|definition=Цепная пара — упорядоченная пара <tex>(A,B)</tex>, в которой <tex>A\Rightarrow ^* B</tex>, используя только цепные правила.}} {{Теорема|statement=Для любой контекстно-свободной (ККС-С) грамматики <tex>G</tex> существует эквивалентная ей ККС-С грамматика <tex>G_1</tex> без цепных правил.

Построим графАлгоритм удаления цепных правил из грамматики: 1) Найти все цепные пары <tex>G</tex>. Вершинами в нем будут нетерминальные символы 2) Для каждой пары <tex>(A, а ребро из B)</tex> добавить к правилам <tex>G_1</tex> все правила вида <tex>A\rightarrow\alpha</tex> в , где <tex>B\rightarrow\alpha</tex> будет тогда и только тогда, когда есть {{---}} нецепное правило из <tex>G</tex>. Найти все цепные пары можно по индукции: '''Базис.''' <tex>(A,A \to B)</tex>. Сделаем транзитивное замыкание {{---}} цепная пара для этого графа и добавим правилалюбого нетерминала, соответствующие новым ребрамтак как <tex>A\Rightarrow ^* A</tex> за ноль шагов. Заметим, что теперь любое выводимое слово можно вывести, используя не более одного  '''цепного правилаИндукция.''' подряд. Также нетрудно понятьЕсли пара <tex>(A,B)</tex> {{---}} цепная, и есть правило <tex>B\rightarrow C</tex>, то <tex>(A, что новая грамматика эквивалентна старойC)</tex> {{---}} цепная пара.

ДалееНетрудно понять, рассмотрим что такой алгоритм найдет все цепные правила грамматики <tex>A \to B</tex>. Пусть из <tex>B</tex> можно вывести: <tex>B \to \alpha_1 \mid \alpha_2 \mid \dots \mid \alpha_nG</tex>, и только их.

Тогда добавим следующее правило в нашу грамматику: Докажем, что, если грамматика <tex>G_1</tex> построена по грамматике <tex>G</tex> с помощью данного алгоритма, то <tex>L(G_1)=L(G)</tex>A , то есть <tex>w\to in L(G_1)</tex> тогда и только тогда, когда <tex>w\alpha_1 \mid \alpha_2 \mid \dots \mid \alpha_nin L(G)</tex>. При этом получившаяся грамматика будет тоже эквивалентна исходной.

Заметим''Достаточность.'' Предположим, что теперь любое слово можно вывести, не используя <tex>S\Rightarrow _{G_1}^* w</tex>. Так как каждое правило <tex>G_1</tex> эквивалентно последовательности из нуля или нескольких цепных правил вовсе<tex>G</tex>, за которой следует нецепное правило из <tex>G</tex>, то из <tex>\alpha\Rightarrow _{G_1}\beta</tex> следует <tex>\alpha\Rightarrow _G^*\beta</tex>. Поэтому удалим ихТаким образом, каждый шаг порождения в <tex>G_1</tex> может быть заменен одним или несколькими шагами в <tex>G</tex>. Собрав эти последовательности шагов, получим, что <tex>S\Rightarrow _G^* w</tex>.

Итого''Необходимость.'' Предположим, была построена К-С грамматика без что <tex>w\in L(G)</tex>. Тогда <tex>w</tex> имеет левое порождение <tex>S\Rightarrow _{lm}^* w</tex>. Где бы в левом порождении не использовалась цепное правило, переменная в правой части становится крайней слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в <tex>G</tex> можно разбить на последовательность "шагов", в которых ноль или несколько цепных правилсопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой "шаг". Но по построению <tex>G_1</tex> каждый из этих шагов может быть выполнен одним ее правилом. Таким образом, эквивалентная исходной<tex>S\Rightarrow _{G_1}^* w</tex>.