Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 43

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 37 38 39 40 41 42 < 43 > 44 45 46 47 48 49 .. 101 >> Следующая


Замечание. Ясно, что язык 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 = {апЬпсп}; мы видели, что этот язык не является КС-языком. Из приведенных примеров следует, что пересечение двух КС-языков может быть, но не обязательно является КС-языком.
Предыдущая << 1 .. 37 38 39 40 41 42 < 43 > 44 45 46 47 48 49 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed