Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

Р — правила грамматики

или конечное множество цепочек

ви­

да ф—>-ф, где ф, г|з — слова

в словаре

V, и цепочка ф содержит

по

крайней мере один символ из словаря

VH. Конечное, двуместное

от­

ношение

—*• интерпретируется как «заменить ф на т|э», или «поста­

вить г|з вместо ф». Это отношение'ТЬбладает

свойствами асимметрич­

ности и

иррефлексивности. Цепочки вида

ф — н а з ы в а ю т с я пра­

Если задана грамматика

G =

(VT ,

VH, Р, S),

то будем говорить:

1. Цепочка

«а получается

(непосредственно)

из

цепочки о/ при­

менением правила ф—мр, если ю = |1ф|г, со' = Ъ^Ъ,

и

{ф—м|з}еР.

2. Последовательность цепочек

ф =

фо, Фь фг, • • •, Фп = "ф ( « ^ 1 )

есть

ф — вывод

цепочки

г|э,

если

для

каждого

i фг+i следует из фг-,

где

O ^ i ^ n .

Наличие

ф вывода

цепочки я|;

будем

обозначать

Ф =

> г|).'

есть цепочка в словаре

VT, и ни к одному из символов FT

не при­

менимо ни одно из правил грамматики

G).

Множество

цепочек,

выводимых в

грамматике G,

называется

*. языком,

порожденным

этой

грамматикой, и

обозначается

L(G).

Язык L(G)

называется терминальным, если L — множество тер­

минальных цепочек грамматики G.

Условимся при написании конкретных грамматик, если это не

оговорено особо, первыми строчными латинскими буквами

а,

Ь, ...

обозначать элементы терминального

словаря

VT ,

элементы

нетер­

минального словаря VH

— прописными латинскими буквами А,

В, ...

а элементы общего словаря

V — строчными

греческими

буквами

а, р, ...

Предложения,

составленные

из этих символов, будем обо­

значать

последними буквами

соответствующих

алфавитов,

т. е.

х, у, ... — предложения, составленные

из элементов

терминально­

го словаря, X,

Y, ... — предложения из элементов

нетерминально­

го словаря, со, ф, г|), ... — предложения из элементов

общего сло­

варя.

чает, что имеется в виду множество

всех

цепочек, которые могут

быть получены из символов множества V.

Рассмотрим введенные понятия на примере.

Пусть задана грамматика G =

(VT,

VB,

Р, S), где

V^{a,

b);

VH — {А,

В,

С};

P =

{C-+ab,

C-+aCb}.

Пусть

со =

aCb, о/ =

aaCbb.

применения одного

правила.

ср — вывод: aCb,

aaCbb, aaaCbbb, aaaabbbb. Последняя

цепочка

является терминальной. Длина вывода равняется трем.

Из приведенного примера видно, что порождающая грамматика

не является

алгоритмом.

Правила

подстановки

грамматики — это не последовательность

предписаний, а совокупность разрешений. Это означает:

1. Правило вида ср—>-гр понимается в грамматике как «ср мож­

но заменить на гр» (а можно и не заменять), тогда как в

алгоритме

оно означало бы «ср следует заменить на гр» (нельзя

не

заменить).

2. Порядок применения правил в грамматике произволен, тогда

как в алгоритме был бы

задан жесткий порядок

применения от­

дельных инструкций.

Две грамматики—Gi и G2 — называются слабо эквивалентны­

ми, если они порождают

один и тот же язык, Ьог

=

L G

2 ;

или две

грамматики

называются

слабо эквивалентными,

если

совпадает

ков,

порождаемых соответственно

четырьмя

типами

грамматик.

Эти

грамматики выделяются путем

наложения

последовательно

усиливающихся ограничений на систему правил Р.

Грамматика называется

грамматикой

типа 0

в

тех случаях,

когда не накладывается никаких

ограничений на

правила ср—>-гр,

где ср и гр могут быть любыми цепочками из словаря V.

Грамматика называется

грамматикой

типа 1, если

в системе Р

правила ср—>-г|) удовлетворяют

условию

ср =

cpHcp2, гр = cpicocp2,

где А — нетерминальный символ, а ср, гр, со — цепочка из словаря V.

Таким образом, в грамматиках типа / отдельный

нетерминальный

символ А переходит в непустую цепочку со в контексте cpt и ср2

(cpi и

ф2 могут быть пустыми цепочками). Грамматики

типа

/ называют

контекстными грамматиками.

Грамматика называется

грамматикой

типа 2 — бесконтекстной,

если в системе правил Р допустимы,

лишь

правила

вида

А—ко,

где

А — нетерминальный символ,

а

со — непустая

цепочка

из V.

7-1861 ...

97

Согласно правилам

этой

грамматики,

замена Л

на со происходит

независимо от контекста.

Грамматика

называется грамматикой

типа 3,

когда допустимы

лишь правила вида А —*-со ,где со =

аВ,

либо со =

а.

Введенные здесь классы могут быть разбиты на подклассы. Та­

кое разделение будет рассмотрено далее.

Упражнения:

1. Пусть

G=

(VT, VB,

Р,

S)—порождающая

грамматика, где

Vr = {a, d,

е},

V*=

{В,

С,

S},

Р = {S-^aB,

B—*Cd, С—*е}.

2.

Пусть

G = (Vr,

Vb,

Р,

S),

где

VT = {a, d, е},

Vn=

{В,

С, S},

Р = { 5 — > а В , В—>Cd,

В—>dC,

С—>

е) . Определить

терминаль­

ные цепочки, порождаемые

данной

грамматикой,

и длину их вы­

вода.

3. Для грамматики G известны ее общий

словарь V = {А,

В, С,

D, Е} и схема правил Р=

{E—+DCD,

Е—+А,

D—+BC,D—+C,

А—УВВ}.

Определить

состав

терминального и нетерминального

словарей,

цель

грамматики,

построить

язык L (G) и определить

длину выводов для каждой терминальной цепочки.

4. Определить, являются ли порождающими следующие грам­

матики:

a)

G =

{{А,

В},

{S,

D),

P = {S-*AB,

S->

-+ASD,

SD-+B,

B^AS),

S);

b)

G =

[{A,

B],

{S},

P={S-+ASBAS,

S-+AB,

AS-+B},

S);

c)

G=

{{В,

C),

[A,

S\,

P={S->A,

A-+B,

A->CA},

S);

d)

G =

[[B,

C),

{A,

S],

P

=

{S->A,

A-+B, A-+CAC),

S ) .

5.

Дана

грамматика

G =

(VT,

Vn, P,

S), где VT

= {A, B},

VH =

= {S,

D},

P={S-+AB,

S—+ADSB,

D —>-BSB,

DS

—>-B,

D—>-д

} . Показать, что цепочка

АВАВВАВ

принадлежит

множе­

ству

L

(G).

G =

({а,

Ь, с,

d, е),

{А, В, С,

D,

Е}, Р —

6.

Дана

грамматика

{A—^ed,

В^АЬ,

С-^Вс,

C—+dD,

D—>-аЕ,

Е—+Ьс},

С).

Определить, принадлежит ли множеству

L(G)

цепочка

eadabcbc.

7.

Дано

V = {С, S,

а,

Ь) и VT = {а, Ь}. Определить, является ли

грамматикой четверка (Vr,

VH,

Р,

S)

для следующих множеств пра­

вил грамматики:

a)

P =

[C-*b,

S-+aCb}-

b)

Р=[Ь-+а,

C-+Sb\;

c)

р =

{с-^ьсас,

d)

P =

{C-+bC,

CS-*aS,

S-^a}.

8.

Пусть

для

каждого

n^lG

= ({a},

{S—KS"},

5) .

Пока­

зать, что каково бы ни было п, L(Gn)

=

0.

матики, порождающие следующие языки:

a)

язык апЬпап

для

1;

b)

языка™2

д л я п ^ 1 ;

c) язык

апЬп2

для

n r ^ l .

2.2. Грамматики непосредственно составляющих

Неукорачивающие

грамматики

— грамматики,

у которых

для

любого правила с р — с п р а в е д л и в о

соотношение

|ср|=£^ ф| . Пра­

вила

такого вида

также

называются

неукорачивающими.

Рассмотрим

пример

неукорачивающей

грамматики. Пусть

за­

дана

G =

( У Т

,

У Н ,

Р,

S),

где

VT=[a,

b),

VH=[S),

Р = { / ? 1 ,

Ft, F3,

F4 }

: S

aa,

F3:

S ->

aSa,

F2:S^bb,

Ft: S->656.

вил мы получаем новое слово, длина которого не

меньше длины

исходного слова: бааб, 6666, baSab,

bbSbb.

Грамматики

непосредственно

составляющих

— грамматики

Поясним

это на примере. Допустим,

что в неукорачивающей

грамматике

имеет место

правило вида АВ—>ВА,

где А и В — не­

терминальные символы.

Такое правило может быть заменено четырьмя правилами грам­

матики непосредственно

составляющих:

АВ-*\В;

\В-+\2\

12

-+В2;

В2-+ВА,

где

1, 2 новые нетерминальные

символы,

которые не встречаются

ни

в каких

старых правилах.

Последовательное применение

этих

правил равносильно применению правила АВ—*-ВА,

причем такая

замена не может привести к появлению

«лишних»

выводов,

по­

скольку символы 1, 2 — новые.

7*

99