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

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

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

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

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

Алгоритм

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

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

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

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

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

Базис. [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]\Gamma[/math] — контекстно-свободная грамматика. [math]\Gamma'[/math] — грамматика, полученная в результате применения алгоритма к [math]\Gamma[/math]. Тогда [math]L(\Gamma) = L(\Gamma').[/math]

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

[math]\triangleright[/math]

[math]\Rightarrow [/math] Покажем, что [math]L(\Gamma) \subseteq L(\Gamma')[/math]. Пусть [math]w\in L(\Gamma)[/math]. Тогда [math]w[/math] имеет левое порождение [math]S\overset{*}{\underset{lm}{\Rightarrow}} w[/math]. Где бы в левом порождении ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в [math]\Gamma[/math] можно разбить на последовательность шагов, в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой шаг. Но по построению [math]\Gamma'[/math] каждый из этих шагов может быть выполнен одним её правилом. Таким образом, [math]S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w[/math], то есть [math]w\in L(\Gamma')[/math]. [math]\Leftarrow [/math] Покажем, что [math]L(\Gamma') \subseteq L(\Gamma)[/math]. Пусть [math]w\in L(\Gamma')[/math], то есть [math]S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w[/math]. Так как каждое правило [math]\Gamma'[/math] эквивалентно последовательности из нуля или нескольких цепных правил [math]\Gamma[/math], за которой следует нецепное правило из [math]\Gamma[/math], то из [math]\alpha{\underset{\Gamma'}{\Rightarrow}} \beta[/math] следует [math]\alpha\overset{*}{\underset{\Gamma}{\Rightarrow}} \beta[/math]. Таким образом, каждый шаг порождения в [math]\Gamma'[/math] может быть заменен одним или несколькими шагами в [math]\Gamma[/math]. Собрав эти последовательности шагов, получим, что [math]S\overset{*}{\underset{\Gamma}{\Rightarrow}} w[/math], то есть [math]w\in L(\Gamma)[/math].

[math]\triangleleft[/math]

Время работы алгоритма

Данный алгоритм работает за [math]O(\left| \Gamma \right| ^ 2)[/math].

Пример

Рассмотрим грамматику: [math] \begin{array}{l l} A\rightarrow B|a\\ B\rightarrow C|b\\ C\rightarrow DD|c \end{array}[/math], в которой есть два цепных правила [math]A\rightarrow B[/math] и [math]B\rightarrow C[/math].

1. Для каждого нетерминала создадим цепную пару. Теперь множество цепных пар будет состоять из [math](A, A)[/math], [math](B, B)[/math], [math](C, C)[/math] и [math](D, D)[/math].
2. Рассмотрим цепное правило [math]A\rightarrow B[/math]. Так как существует цепная пара [math](A, A)[/math], второй элемент которой совпадает с левым нетерминалом из правила,
   добавим в множество пару [math](A, B)[/math], у которой первый элемент такой же как у найденной, а второй равен правому нетерминалу из текущего правила.
3. Повторим второй пункт для правила [math]B\rightarrow C[/math] и пары [math](B, B)[/math]. Теперь множество цепных пар будет состоять из [math](A, A)[/math], [math](B, B)[/math], [math](C, C)[/math], [math](D, D)[/math], [math](A, B)[/math] и [math](B, C)[/math].
4. Повторим второй пункт для правила [math]B\rightarrow C[/math] и пары [math](A, B)[/math], и получим множество [math]\lbrace (A, A), (B, B), (C, C), (D, D), (A, B), (B, C), (A, C)\rbrace[/math].
5. Для каждой пары добавим в [math]\Gamma'[/math] новые правила:
   • [math]A\rightarrow b[/math] для [math](A, B)[/math]
   • [math]A\rightarrow c[/math] и [math]A\rightarrow DD[/math] для [math](A, C)[/math]
   • [math]B\rightarrow c[/math] и [math]B\rightarrow DD[/math] для [math](B, C)[/math]
   • Оставшиеся цепные пары новых правил не добавят.

См. также

• Контекстно-свободные грамматики
• Нормальная форма Хомского
• Chomsky normal form

Литература

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