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

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

Цепное правило — правило вида [math]A\rightarrow B[/math], где [math]A[/math] и [math]B[/math] — нетерминалы.

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

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

Алгоритм

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

Цепная пара — упорядоченная пара [math](A,B)[/math], в которой [math]A\Rightarrow ^* B[/math], используя только цепные правила.

Алгоритм удаления цепных правил из грамматики:

1. Найти все цепные пары в грамматике [math]\Gamma[/math].
2. Для каждой цепной пары [math](A,B)[/math] добавить в грамматику [math]\Gamma_1[/math] все правила вида [math]A\rightarrow\alpha[/math], где [math]B\rightarrow\alpha[/math] — нецепное правило из [math]\Gamma[/math].

Найти все цепные пары можно по индукции:

Базис. [math](A,A)[/math] — цепная пара для любого нетерминала, так как [math]A\Rightarrow ^* A[/math] за ноль шагов.

Индукция. Если пара [math](A,B)[/math] — цепная, и есть правило [math]B\rightarrow C[/math], то [math](A,C)[/math] — цепная пара.

Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики [math]\Gamma[/math], и только их.

Корректность алгоритма

Теорема:

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

Доказательство:

[math]\triangleright[/math]

Докажем, что, если грамматика [math]G_1[/math] построена по грамматике [math]G[/math] с помощью описанного выше алгоритма, то [math]L(G_1)=L(G)[/math], то есть [math]w\in L(G_1)[/math] тогда и только тогда, когда [math]w\in L(G)[/math]. Достаточность. Предположим, [math]S\Rightarrow _{G_1}^* w[/math]. Так как каждое правило [math]G_1[/math] эквивалентно последовательности из нуля или нескольких цепных правил [math]G[/math], за которой следует нецепное правило из [math]G[/math], то из [math]\alpha\Rightarrow _{G_1}\beta[/math] следует [math]\alpha\Rightarrow _G^*\beta[/math]. Таким образом, каждый шаг порождения в [math]G_1[/math] может быть заменен одним или несколькими шагами в [math]G[/math]. Собрав эти последовательности шагов, получим, что [math]S\Rightarrow _G^* w[/math]. Необходимость. Предположим, что [math]w\in L(G)[/math]. Тогда [math]w[/math] имеет левое порождение [math]S\Rightarrow _{lm}^* w[/math]. Где бы в левом порождении ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в [math]G[/math] можно разбить на последовательность "шагов", в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой "шаг". Но по построению [math]G_1[/math] каждый из этих шагов может быть выполнен одним ее правилом. Таким образом, [math]S\Rightarrow _{G_1}^* w[/math].

[math]\triangleleft[/math]

Литература

• Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)