Правая часть каждого Р-правила начинается терминалом, как и должно быть, так как F - наибольший нетерминал в этом упорядочении. Предшествующий ему нетерминал Т имеет правила Т -F \ FT, так что, заменив в них F, получаем Т{Е)\а\{Е)Т \ аТ. Переходя к Т\ обнаруживаем, что здесь ничего менять не надо. Затем заменяем £-правила правилами

£->(£) I й I {£) Т I аТ I {£) Е \ аЕ \ [Е] ТЕ \ аГЕ

В -правилах ничего менять не надо.

На шагах (5) и (6) появляются новый нетерминал ) и правило )-»-), поэтому все вхождения ) в предыдущих правилах надо заменить на ). Таким образом, в результате получится грамматика в нормальной форме Грейбах с правилами

Е {Еу \ а\ (ЕуТ \ аТ \ {ЕУ Е \аЕ \ (Е) ТЕ \аГЕ Е ~ + Т\ТЕ Т(Еу\а\{ЕуТ\аТ Т --x-Fl-FT F(Ey \а

□

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

2.4.5. Другой метод преобразования к нормальной форме Грейбах

Изложим другой способ построения грамматики, в которой каждое правило имеет вид Л аа. Здесь грамматика переписывается только один раз. Пусть G = (N, 2, Я, 5)~КС-грам-матика, в которой нет е-правил (даже вида 5->е) и цепных правил.

Вместо того чтобы описывать этот метод в терминах правил, воспользуемся системами определяющих уравнений того типа, что был введен в разд. 2.2.2. Например, множество правил

ЛЛаВ\ВВ\Ь BaA\BAa\Bd\c

(2.4.6)

можно представить в виде системы уравнений А ---АаВ + ВВЬ B=aABAaBd+c

где А и В - неизвестные, представляющие множества.

Определение. Пусть Д и S-два непересекающихся алфавита. Системой определяющих уравнений в алфавитах S и Д назовем систему уравнений вида Д = « + «2 + • • •где Л G А и a/G(All2)*. Если kO, то уравнение имеет вид Л = 0. Для каждого Л G Д в системе есть одно уравнение. Решением системы определяющих уравнений назовем такое отображение / множестваД в 5(2*), что если подставить f [А] в каждое уравнение вместо каждого Л G Д, уравнения станут равенствами. Решение / назовем наименьшей неподвижной точкой, если f{A) eg-(Л) для любого решения g и любого ЛД-

Чтобы получить КС-грамматику, соответствующую системе определяющих уравнений, надо для каждого уравнения - Л = ...-hcc/j построить правила А-а\а1.. .\af. Нетерминалами будут символы алфавита Д. Очевидно, что это соответствие взаимно однозначно. Приведем несколько результатов о системах определяющих уравнений, обобщающих результаты о стандартных системах уравнений с регулярными коэффициентами (частном случае систем-определяющих уравнений). Доказательства оставим в качестве упражнений.

Лемма 2.17. Ншшеньшая неподвижная точка системы определяющих уравнений в алфавитах Д w S единственна и имеет вид / (Л) {ш Л =>оШ и w*}, где G соответствующая КС-грамматика.

Доказательство. Упражнение. □

Мы будем пользоваться матричным представлением систем определяющих уравнений. Допустим, что Д {Л, Л, Л,,}. Матричное уравнение

A = ARH В

представляет п уравнений. Здесь Л - вектор-строка [А, А, Л„], R - матрица порядка п, элементами которой служат регулярные выражения, и В - вектор-строка, состоящая из п регулярных выражений.

В качестве «скалярного» умножения возьмем конкатенацию, а в качестве сложения - операцию + (т. е. объединение). Сложение и умножение векторов и матриц определяются, как обычно. Элементом матрицы R, стоящим в i-й строке и j-u столбце, будет регулярное выражение а~\-.. .-\-cif, если Аа, . . ., Ла,,- все члены уравнения для Aj, первым символом которых является Л,-. В качестве j-u компоненты вектора В возьмем сумму тех членов уравнения для Aj, которые начинаются символом из множества 2. Таким образом, Bj и -такие выражения, что уравнение для Aj (в КС-грамматнке ему соответствует множе-

ство Лу-правил) можно записать в виде

Aj AJj -V Л,;?,у Н- ... + Л fi,j + ... Н- A,R,j 4- Bj

где Bj-сумма выражений, начинающихся терминалами. Система определяющих уравнений (2.4.6) примет вид

\аВ 0 В Aa + d\

(2.4.7) [Л, В] = [А, В]

+ [6, аА-\-с]

Теперь для матричного уравнения AAR-B найде.м такую эквивалентную систему определяющих уравнений, что все правые части соответствующих ей правил начинаются терминальными символами.

Этот переход основан на следующей лемме:

Лемма 2.18. Пусть А -AR + B-система определяющих уравнений. Тогда ее наименьшей неподвижной точкой будет A = BR*, где R* = I + R + R- "Ь R "Г • > -единичная матрица {е на диагонали и 0-е остальных местах), R- -RR, R3 RRR и т. д.

Доказательство. Упражнение. □

Если положить R" - RR*, то наименьшую неподвижную точку матричного уравнения A = AR -В можно записать в виде A-B(R+ + I) = BR+ + B1-BR+ + B. К сожалению, для этой системы нельзя найти соответствующую грамматику: она не является системой определяющих уравнений, так как элементы матрицы R могут быть бесконечными суммами членов исходных уравнений. Однако R+ можно заменить новой матрицей „неизвестных" Q, каждый элемент которой, расположенный в 1-й строке и /-М столбце,- это новый символ.

Тогда, заметив, что R+RR + R, можно получить систему определяющих уравнений Q=RQ-hR с неизвестными gj. Отметим, что если Q и R - матрицы порядка п, то система состоит из п- уравнений.

Лемма 2.19. Пусть AAR + B-система определяющих уравнений в алфавитах А « 2. Пусть Q -матрица того же порядка, что и R, причем все ее элементы-различные новые символы. Тогда система определяющих уравнений, состоящая из А - BQ+B и Q = RQ-i-R, имеет наименьшую нвподвиоюную точку, которая совпадает на Л. с наименьшей неподвижной точкой системы A-AR + B.

Доказательство. Упражнение. □

Дадим другой алгоритм преобразования приведенной грамматики к нормальной форме Грейбах.

186

Алгоритм 2.15. Преобразование к нормальной форме Грейбах.

Вход. Приведенная грамматика G(N, 2, Р, 5) без правил вида S-e.

Выход. Эквивалентная грамматика G = (N, 2, Р S) в нормальной форме Грейбах. Метод.

(1) По грамматике G построить систему определяющих уравнений AARhB в алфавитах N и 2.

(2) Пусть Q -матрица порядка п, состоящая из новых символов, и 4iN = /2. Построить новую систему определяющих уравнений А - BQ-f В, Q - RQ + R и соответствующую грамматику G. Так как в векторе В каждая компонента, отличная от 0, начинается терминалом, а такие компоненты должны быть в силу приведенности грамматики G, то для ЛN все Л-правила грамматикиG будут начинаться терминалами.

(3) Так как G -приведенная грамматика, то е не является элементом матрицы R. Поэтому для каждого элемента д матрицы Q все соответствующие д-правпла грамлатики G, начинаются символами из NU2. В тех правых частях этих правил, которые начинаются нетерминалом, заменить этот нетерминал Л правыми частями всех Л-правил. В результате получится грамматика, у которой правые части всех правил начинаются терминалом.

(4) Если в правой части некоторого правила терминал а встречается не на первом месте, заменить его новым нетерминалом а и добавить правило а~>-а. Результирующую грамматику обозначить через G. □

Теорема 2.20. Алгоритм 2.15 дает грамматику G в нормальной форме Грейбах и L{G) = L(G).

Доказательство. Так как грамматика G приведенная и не содержит S->е, то G -грамматика в нормальной форме Грейбах, поскольку е не является компонентой вектора В и матрпгсы R. Из лемм 2.14, 2.17 и 2.19 следует, что L{G) =

Пример 2.30. Рассмотрим грамматику, соответствующую системе определяющих уравнений (2.4.7):

Л АаВ \ВВ\Ь BaA\BAa\Bd\c

Перепишем систему (2.4.7), согласно шагу (2) алгоритма 2.15, в виде

(2.4.8) [Л, В][Ь, аЛ+<:][

Затем добавим систему (2.4.9)

Системам (2.4.8) и (2.4.9) соответствует грамматика

А ~bW\aAy\cy\b -bX\aAZ\cZ\aA\c

В

Х-у Z

aBW\aB аВХ

BW\Aay\dy\B BX]AaZ\dZ\Aa\d

Заметим, что X - бесполезный символ. На шаге (3) в правилах Y-BW\Aay\B и ZBX\AaZ\Aa нетерминалы А и 5 заменяются соответствующими правыми частями правил. Так как это преобразование и преобразование на шаге (4) уже знакомы читателю, мы их опускаем. □

УПРАЖНЕНИЯ

2.4.1. Пусть G определяется правилами

5 -> Д5 ААа\ ЬВ B->a\Sb

Постройте деревья выводов следующих выводимых цепочек:

(а) baabaab,

(б) ЬВАВЬ,

(в) baSb.

2.4.2. Постройте левый и правый выводы цепочки baabaab в грамматике из упр. 2.4.1.

2.4.3. Постройте все сечения дерева, изображенного на рис. 2.14.

Рис. 2.14. Непомеченное дерево вывода

2.4.4. Покажите, что следующие утверждения о КС-грамматике G и цепочке ш эквивалентны;

(а) W-крона двух различных деревьев выводов в G,

(б) W имеет два различных левых вывода в G,

(в) W имеет два различных правых вывода в G.

**2.4.5. Каково наибольшее число выводов, которые представляются одни.м и тем же деревом с п вершинами?

2.4.6. Преобразуйте грамматику

SA\B AaB\bS\b В~АВ\Ва B-AS\b

в эквивалентную КС-грамматику, не содержащую бесполезных символов.

2.4.7. Докажите, что алгоритм 2.8 правильно устраняет недостижимые символы.

2.4.8. Дополните доказательство теоремы 2.13.

2.4.9. Оцените временную и емкостную сложности алгоритма 2.8. В качестве вычислительной модели возьмите машину с произвольным доступом к памяти.

2.4.10. Постройте алгориТхМ, вычисляющий для КС-грамма-тики G---(N, S, Р, S) множество {ЛЛ=Ф*е, ЛGN}. Насколько быстр Ваш алгоритм?

2.4.11. Найдите грамматику без е-правил, эквивалентную грамматике

S-*ABC A-BBle В-уСС\а C~AAlb

2.4.12. Дополните Доказательство теоремы 2.14.

2.4.13. Найдите приведенную грамматику, эквивалентную грамматике

в-с-

D~ Е-

-А\В

C\D

D\E

S\a\e

S\c\e

2.4.14. Докажите теорему 2.16.

2.4.15. Докажите лемму 2.14.