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

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

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


Для обозначения языков Хомского и грамматик Хомского мы будем использовать сокращения «КС-языки» и «КС-грамматики» (КС — от «контекстно-свободный»).

7.2.1. Определения

Грамматика Хомского, или КС-грамматика, задается указанием следующих четырех объектов:

. Конечное множество символов Vt — терминальный, или основной, словарь.

.. Конечное множество символов Va — вспомогательный словарь. ... Аксиома 5 є Va-

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

Ae= Va, 9 є (VaUVt)-. Гл. VII. Контекстно-свободные языки

117

Таким образом, комбинаторная система, соответствующая грамматике Хомского, является полутуэвской системой, однако специального вида. Эта система имеет «нетерминальные» и, возможно, «терминальные» теоремы1). Языком Хомского называется множество терминальных теорем полутуэвской системы, иначе говоря, множество фраз над терминальным словарем некоторой грамматики Хомского, порождаемых этой грамматикой.

Применительно к грамматикам Хомского вместо «доказательство» принято говорить «вывод».

Примеры. 1. Пусть имеется грамматика Gm: VA = {S}-, Vt = {a,b, с}\ S-*aSa S->bSb . S-* с

Один из возможных выводов в Gm:

S -> aSa -> aaSaa -* aabSbaa -* aabcbaa.

Мы будем писать

S =^ aabcbaa;

запись ф=^^ означает, что существует вывод, начинающийся цепочкой ф и заканчивающийся цепочкой

Ясно, что грамматика Gm порождает в точности те фразы, которые построены по схеме хтх, где х — любая цепочка из символов а и b, а х— ее обращение (зеркальный образ). Это можно записать так:

Lm = L(Gm) = {хсх I х<={а, Ь}*}.

2. Пусть имеется грамматика Go-.

Va = {S,A}; VT = {a,b); S-* а А A-* Ab •

Очевидно, что выводы в этой грамматике продолжаются бесконечно, не приводя к терминальным цепочкам: Go порождает пустой язык.

Классификация правил. Всякая КС-грамматика G порождает некоторое множество нетерминальных цепочек и некоторое (быть может, пустое) множество терминальных цепочек,

') Т. е. теоремы, являющиеся цепочками в Va U Vt, но не в Vt (соответственно цепочками в Vт)- — Прим ред. 118

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

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

Необходимым условием непустоты языка L(G) является наличие в G одного или нескольких терминальных правил вида

А —> т,

где А є V А, т є Vt-

Все прочие правила грамматики называются нетерминальными.

Пример. Грамматика Gm имеет два нетерминальных правила: S-*aSa и S-*bSb

и одно терминальное:

S-* с.

Грамматика G0 не имеет ни одного терминального правила.

7.2.2. Соответствие между грамматиками и языками

Таким образом, всякой КС-грамматике соответствует некоторый КС-язык, быть может, пустой. Важно подчеркнуть, что это соответствие не является взаимно однозначным: различные грамматики могут порождать один и тот же язык.

Пример. Пусть имеется грамматика Gn-.

Va = {S, A}; Vt = {а, Ь, с};

S-*aSa (!)
S-*bSb (2)
S ->с (3)
S -*abSba (4)
Sс А (5)
S->aA (6)

Грамматика Gn порождает тот же язык Lm, что и Gm, однако отличается от этой последней

. добавлением правила (4), которое обеспечивает «более быстрое» порождение некоторых цепочек языка Lm',

.. добавлением правил (5) и (o), которые вообще не дают никаких терминальных цепочек.

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

Итак, пусть дана некоторая грамматика. Мы можем прежде всего, не подвергая ее существенному изменению (т. е. не меняя порождаемого ею языка), произвести над ней следующие преобразования: Гл. VII. Контекстно-свободные языки

119

1) «очистить» грамматику, выбросив из нее те правила и символы, которые не ведут к терминальным цепочкам;

2) тем или иным образом перестроить ее правила, сохраняя порождаемый ею язык.

Связные грамматики. При рассмотрении грамматики удобно сопоставлять ей граф, вершины которого соответствуют символам нетерминального словаря:

S = Ai, A2, .. •, Ар, и символам, фигурирующим в терминальных правилах:

а2, . . ., Clq.

Мы будем проводить дугу из Ai в Aj (соответственно в ak), если в грамматике имеется правило вида

At-+q>Ajty (соответственно Ai-Xik).

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

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

О пустой цепочке. Никакие принципиальные соображения не мешают нам иметь терминальные правила вида

А-+Е,

где E — пустая цепочка.

Однако в техническом отношении оказывается более удобным устранить такие правила. Можно доказать (см. посвященные этому упражнения), что любой КС-грамматике, которая порождает язык L, содержащий пустую цепочку, можно поставить в соответствие «очень близкую к ней» КС-грамматику, порождающую язык L\{E}. В последующем изложении мы будем предполагать, что эта редукция выполнена.
Предыдущая << 1 .. 35 36 37 38 39 40 < 41 > 42 43 44 45 46 47 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed