Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Замечание. Ясно, что язык L = {апЬпсп} рекурсивен. Следовательно,
класс КС-языков является собственным подклассом класса рекурсивных языков.
7.2.6. Упражнения
1. Построить КС-грамматики, порождающие языки
Ll=WbnCp] и L2 = {amb9c%
2. Построить КС-грамматику, порождающую язык {хх} над алфавитом {a, b} (без метки в середине).
3. Доказать, что язык {aPb^C | р KqfC г] не является КС-языком.
4. Рассмотрим словарь V = Va U Vt и правила вида A-* ф, А е Va- Будем брать в качестве аксиом один за другим все элементы словаря Va- Могут ли при этом порождаться разные языки? Построить простые примеры. Вот один из них:
A^ AC
В-*ВС
A^-Aa
А^-а
B^-Bb
В-*Ь
C^AA
5. Элиминация пустой цепочки. Пусть G есть КС-грамматика, и пусть Vo — множество символов a Vа, таких, что для них имеются правила вида А—*Е. Образуем множество Vi, добавив к V0 все А е Va, такие, что имеются правила вида A-* ф, где фє Vo; аналогично определим V% и т. д.
Рассмотреть полученную последовательность множеств. Сформулировать условия, необходимые и достаточные для того, чтобы E є L(G). Исходя из G, построить КС-грамматику G', такую, что
L(G') = L(G)\{?}.Гл. VII. Контекстно-свободные языки
123
Заметим, что для этого недостаточно просто устранить все правила вида А -*Е. В самом деле, рассмотрим грамматику
S->-аЛа
G:
¦Е ¦ЬА
A-A-
А-*с
Если выкинуть из G правило Л-+?, то G не будет порождать ни цепочку аа, ни цепочку аЬпа. Ясно, однако, что свойство порождать эти цепочки должно быть сохранено.
6. Элиминация непродуктивных правил. Пустой язык. Пусть G есть КС-грамматика. Будем считать, что в G нет правил вида А-*Е.
Обозначим через W0 объединение терминального словаря Vt и множества символов А, таких, что А є Va и имеются правила вида А —* X, где т — терминальная цепочка. Образуем множество Wu добавив к Wo все А є VА, такие, что имеются правила вида
A-*q>, где q>^Wl\{E}.
Поступая аналогично, образуем последовательность множеств W і.
Используя множества Wu сформулировать условие, необходимое и достаточное для того, чтобы язык L(G) был пуст.
Указать процедуру, позволяющую устранить из грамматики все «непродуктивные» правила.
Заметим, что для грамматики
S-* BaB
G:
B-* Bb
B-A-
b
ASA
¦а
множества Wo и Wi суть соответственно {А, В) и {А, В, 5}; однако если S — аксиома, то символ А «непродуктивен», поскольку его нельзя получить из S. Дело будет обстоять иначе, если добавить к этой грамматике правило вида S-> фЛ'ф.
7. Используя предыдущее упражнение, указать процедуру, позволяющую распознавать, является ли множество порождаемых грамматикой терминальных цепочек бесконечным.
§ 7.3. СВОЙСТВА ЗАМКНУТОСТИ
Говорят, что множество замкнуто относительно некоторой операции, если результат применения этой операции к любому элементу множества (если операция унарна) или к любой паре124
Часть II. Некоторые замечательные классы языков
элементов (если операция бинарна) и т. п. содержится в этом множестве. Рассмотрим с этой точки зрения некоторые простые операции над КС-языками.
7.3.1. Объединение КС-языков
Пусть Li и L2 суть КС-языки, заданные соответственно грамматиками Gi и G2 с аксиомами Si и S2. Изменив, если нужно, обозначения некоторых или всех вспомогательных символов, можно добиться, чтобы
VА, П VA,
Рассмотрим грамматику с аксиомой
S ф Fa, U VА„
правилами которой будут все правила грамматик Gi и G2 и сверх того правила S-»Si и S-»S2.
Ясно, что это КС-грамматика, и она порождает язык L1 U L2 Итак, объединение двух КС-языков является КС-языком.
7.3.2. Произведение КС-языков
Сохраняя те же обозначения, определим произведение LiL2. Для этого, как и выше, сделаем так, чтобы пересечение вспомогательных словарей грамматик Gi и G2 было пусто. Затем возьмем в качестве аксиомы новый символ S, объединим множества правил обеих грамматик и добавим к этому объединению правило S-* —> StS2. Ясно, что таким образом мы построили КС-грамматику, порождающую LiL2. Итак, произведение двух КС-языков является КС-языком.
7.3.3. Итерация
Только что полученный результат позволяет по КС-грамматике, порождающей язык L, строить КС-грамматики, порождающие языки L2, L3 и т. д. Рассмотрим теперь язык
L'\{E} = L UL2U^3U ... ULnU ....
Пусть S—аксиома КС-грамматики G, порождающей L. Добавим к G новый символ T и правила T-+ST, T-+S; кроме того, объявим T аксиомой вместо S. Новые правила позволяют, очевидно, порождать цепочки S, S2, ..., S", ..,из которых по правилам
грамматики G получаются языки L, L2, ..., Ln.....Итак, итвра
ция КС-языка является КС-языком (с точностью до пустой цепочки).
7.3.4. Пересечение КС-языков 1. Рассмотрим КС-языки
L0 = {апса"} и Lm = {хсх \ х е {а, 6}*}
(см. п. 7.2.1). Ясно, что L0 П Lm =• L0,Г л. VII. Контекстно-свободные языки
125
2. Рассмотрим КС-языки
L1-{aW} и L2 = {ambqcq}.
Имеем Li П L2 = {апЬпсп}; мы видели, что этот язык не является КС-языком. Из приведенных примеров следует, что пересечение двух КС-языков может быть, но не обязательно является КС-языком.