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

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

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


7.3.5. Дополнение

Язык Vt является КС-языком, поскольку он может быть порожден с помощью грамматики, содержащей всевозможные правила вида S-*aS, S-*Sa и S-*а.

Под дополнением L языка L мы понимаем дополнение относительно Vt- Известно, что

L1RL2 = L1 UI2-

Поэтому, если бы операция взятия дополнения сохраняла свойство быть КС-языком, то и пересечение сохраняло бы его; следовательно, дополнение КС-языка не обязательно является КС-языком.

7.3.6. Обращение

Операция обращения, примененная к КС-языку L с грамматикой G:{A—>- ф}, ставит ему в соответствие язык L с грамматикой G:{A~*ф}. Ясно, что результат обращения КС-языка является КС-языком.

7.3.7. Подстановка

Пусть имеется КС-язык L, порождаемый грамматикой G со словарем Va U Vt, где Vt = [di | 1 Пусть, далее, имеются

п КС-языков Li, ..., Li, ..., Ln (этих языков столько, сколько

символов в Vt), и пусть Gb ..., Gi.....Gn суть КС-грамматики,

порождающие эти языки. Сделаем так, чтобы все попарные пересечения вспомогательных словарей грамматик G, Gi, ..., Gn были пусты, и отождествим ui с аксиомой грамматики Gt-, задающей Li.

Объединение грамматик О, Gt, ..., Gn является КС-грамматикой, порождающей язык, получаемый из L, Li, ..., Ln посредством операции, называемой подстаножой Li, ..., Ln в L. Итак, результат подстановки КС-языков в КС-язык является КС-языком.

Резюмируем: множество КС-языков замкнуто относительно операций объединения, умножения, итерации, обращения и подстановки.

7.3.8. Упражнение

Пусть имеется КС-язык, заданный грамматикой О. Рассмотрим все языки, которые можно получить, поочередно выбирая в качестве аксиомы каждый из нетерминальных символов грамматики G. 126

Часть II. Некоторые замечательные классы языков

Образуем объединение этих языков. Что получится? Попытайтесь сформулировать выводы относительно роли аксиомы в грамматике.

§ 7.4. СПЕЦИАЛЬНЫЕ КЛАССЫ КС-ЯЗЫКОВ

Вводя дополнительные ограничения на вид КС-правил, можно определить различные классы КС-языков. Эти классы вводятся в силу самых разных соображений и не обязательно обладают свойствами замкнутости, присущими классу всех КС-языков. Некоторые свойства таких специальных классов можно вывести непосредственно из алгебраической характеристики КС-языков, которая будет получена ниже.

Поскольку разные КС-грамматики могут порождать один и тог же язык, при классификации языков необходимо соблюдать некоторые предосторожности.

Мы будем определять грамматику того или иного типа (а), формулируя свойства, которыми должны обладать ее правила.

Будем говорить, что язык L относится к типу (а), если существует хотя бы одна грамматика этого типа, порождающая данный язык.

Таким образом, чтобы доказать, что язык не относится к типу (а), необходимо показать, что он не может быть порожден ни одной грамматикой типа (а).

7.4.1. Автоматные языки

В одной из следующих глав мы подробно будем изучать грамматики, все нетерминальные правила которых имеют вид

А->аВ\ A, Bz=Va, a<=.VT.

В литературе на английском языке такие грамматики принято называть finite-state grammars (по-русски — грамматики с конечным числом состояний); порождаемые ими языки называют также регулярными. Изучение этих языков было начато в известной работе С. К. Клини [1956], в которой была доказана основная теорема о них (см. далее п. 10.4.4).

Мы будем называть грамматики описанного типа автоматным«, сокращенно А-грамматиками1) (по причинам, которые выяснятся позднее, в гл. X).

Языки, порождаемые А-грамматиками, мы будем называть А-языками, или автоматными языками.

') В оригинале «К-грамматики»— от фамилии Kleene. Мы, однако, не сочли возможным отказаться от принятого в русской литературе термина «А-грамма-тики». — Прим. ред. Г л. VII. Контекстно-свободные языки

127

7.4.2. Линейные языки

Грамматика, все нетерминальные правила которой имеют вид

А ->- хВу; А, В є= Va-, х, у <= V'T,

называется линейной.

Язык называется линейным, если он может быть порожден линейной грамматикой.

А-языки образуют подкласс класса линейных языков. Другой интересный подкласс составляют минимальные линейные языки, для которых Va состоит из одного символа S, а множество терминальных правил — из одного правила S-* с, причем символ с не встречается ни в каком другом правиле. Язык Lm из примера на стр. 117 является минимальным линейным языком.

7.4.3. Металинейные языки

КС-грамматика называется металинейной, если правые части ее правил не содержат аксиомы и все правила, левые части которых отличны от аксиомы, имеют такой же вид, как правила линейной грамматики.

Язык называется металинейным, если существует порождающая его металинейная грамматика.

Пример. Рассмотрим язык, заданный словарями Va = (SjT), Vt = [а, Ь, с} и грамматикой

G,



S-»TT Т-*-аТа T^bTb T-* с

G2m — металинейная грамматика. Она порождает «двойной зеркальный язык» L2m = {хсхусу}.

Контрпример. Грамматика

S-»aSS S^b

не является металинейной. Порождаемый ею язык состоит из «скелетов» всевозможных выражений, образованных из предметных символов и символов бинарных операций в так называемой бесскобочной записи (записи Лукасевича). Можно доказать, что этот язык не порождается никакой металинейной грамматикой, т. е. не является металинейным. 128
Предыдущая << 1 .. 38 39 40 41 42 43 < 44 > 45 46 47 48 49 50 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed