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

Пусть имеется терминальный словарь Ут =

{«ь • • •, ап}-

Обозна­

чим через

V't расширенный словарь, в котором каждому

терми­

нальному

символу cii, сопоставлен

символ

а'г: V\ =

{ai, а\,.

..,

ап, а'п). Язык, порождаемый

грамматикой

G = (V'T , {S},

Р,

S),

правила которой имеют вид

S - +A,

Р '' S

->

Sa^a'fS,

называется языком Дика и обозначается буквой Д.

Предложения со этого языка

обладают следующим

свойством:

если каждую пару ща'г (i = 1, 2 , . . . , п) соседних символов,

содер­

жащихся в со, разрешить заменять" пустым символомЛ > т 0

Для каж­

Дика объясняется тем, что

они очевидным образом связаны со

скобочными структурами,

обычными

для естественных

и искусст­

венных языков.

Представим

себе набор

формул

некоторого

математического

вычисления или

программу,

записанную в языке

типа

АЛГОЛ.

Эта операция представляет собой обычное теоретико-множест­

венное объединение; она

коммутативна и

ассоциативна:

L , U Z 2 = Z 2

[j L x

[Lt

U Lt) U LZ=LX

U {La

U Lt).

Li

При тех же условиях пересечением двух

языков

(обозначение:

П -^г) называется

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

менно обоим языкам.

Эта операция представляет

собой

обычное

теоретико-множест­

венное пересечение; она тоже коммутативна и ассоциативна.

Дополнением языка L до Ут называется

множество всех слов,

принадлежащих V*T , но не принадлежащих L .

'Само* множество

V*T

есть язык,

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

до V*T

является пустой язык.

Подчеркнем, что язык, содержащий пустое слово е, не является

пустым.

Операцию дополнения рассмотрим на примере

1 / т = К

Ъ};

L = \атЪп\т^

1, n >

1};

V * T \ L = (L1UL2UL3),

где Li — множество

всех

слов, начинаю­

щихся с Ъ, L 2 — множество всех слов, начинающихся с атЪпа

и L 3 =

=

{а}*, т. е. L 3 есть множество

всех слов, состоящих только

из а.

Отношение языков типов 0,

1, 2, 3 к булевским операциям опре­

типа / по отношению к фиксированному

словарю, остается

откры­

тым.

Теорема

28

(Бар-Хиллела,

Перльса и

Шамира).

Класс языков

типа 2 замкнут

относительно

операций

объединения,

но

не замк­

нут относительно

операции дополнения

по отношению к

словарю,

содержащему

не

менее

двух

символов,

а также

по

отношению

к операции

пересечения.

Теорема

29

(Клини).

Класс языков типа 3 замкнут

относительно

всех булевских

операций.

другие.

Произведением

(конкатенацией)

двух

языков

(обозначение:

Li'Lz)

называется

множество

всех

слов, которые можно

получить

следующим

способом: берется

некоторое слово из L 4

и к нему при­

соединяется

конкатенацией

справа

некоторое

слово из L 2

, т. е.

LiL2 = |Х1

Х% | Хх

е= L l t

^ 2

ё 4 ) .

Эта

операция

(называемая

умножением

языков)

не

совпадает

Пусть Ут = {а, Ь, с}. Рассмотрим

язык

{а}, состоящий из одно­

го однобуквенного слова а. Тогда произведение

L=

v;

есть множество всех слов, начинающихся с а.

Операция итерации (операция Клини).

Поскольку

операция ум­

ножения языков

ассоциативна,

мы можем

возводить

данный язык

в степень:

I

2 = LL, L 3 =

{LL)

L = L

{LL), . . .

Клини предложил рассматривать объединение

I * = Е U L U I Й

U 1Г

U • • • U L " U . . .

V={a,b,...}

как язык, состоящий из однобуквенных слов. Тогда

V2 — множество

всех двубуквенных слов; V3

— множество всех трехбуквенных

и т.д.

Поэтому EU

V-U V2U

V3U

... — есть

множество

всех

слов

над

V,

т. е.

V*.

Доказана

замкнутость

классов

регулярных

и

бесконтекстных

языков относительно

умножения и итерации. Язык L

называется

регулярным,

если существует конечный автомат

А,

такой,

что

L =

L(A).

Пусть

дан язык LcrF* T ;

через L T обозначается

язык,

состоя­

щий из обращений всех слов языка L :

U

=

{ХТ\Х^Ц.

Эта операция

является

инвалютивной

(т. е. совпадает

со своей

обратной

операцией):

(ZT )T =

I .

Кроме того, она

связана

с умножением

языков

следующим со­

отношением:

[LMY

=

MTL\

Например, язык

V * T ( V * T ) T совпадает с V*T, поскольку

( У * т ) т =

= V*T

и

£ E V » , .

Введем теперь понятие об операции

гомоморфизма.

Поставим в соответствие элементу а

словаря VT конечный сло­

варь

VTa.

Обозначим через V*Ta множество всех цепочек из

словаря

V T a , а через

х(а) —какую-либо

цепочку

из -V*T a .

Таким

образом,

функция т определена на отдельных символах а из словаря

VT. Оп­

ределим теперь функцию т на предложениях из словаря V? следую­

щим образом: если А: = aixah

...

ais,

то

х(х)

= т(аг'1 )г(ш'2 )

. . . x(ais).

Так, определенная функция х отображает подмножество цепо­

чек L

из

V*T

в некоторое

подмножество

цепочек

из

(U УТ а)*, т. е.

T(L)

=

( U F T a ) * .

а

отображения языка L

с помощью функции х на­

Операция x(L)

зывается операцией

гомоморфизма.

Теорема 31 (Бар-Хиллела,

Перльса

и Шамира).

Классы языков

типа 0, 2 я 3

замкнуты относительно операции гомоморфизма.

Для

языков

же

типа /

(контекстных) имеет

место следующая

теорема.

Теорема 32

(Гинсбурга

и Роуза).

Если Ут содержит хотя бы два

элемента, то класс контекстных языков

не

замкнут

относительно

операции гомоморфизма.

Проекция

языка.

Для

каждого

слова

в алфавите X X Y

< х ( 1 ) г / ( 1 ) > 0 ( 2 ) я 2 ) > . . .

<x(t)y(t)>

Цилиндр

языка. Пусть заданы алфавит У и язык L в алфавите X.

У-цилиндром

языка L называется язык U,

состоящий из всех слов

в алфавите X X Y, X проекции которых принадлежат L .

Свойства

языков по отношению к рассмотренным

операциям

сведены в табл. 1.

Т а б л и ц а 1

}& п/п

Тип языка

Операция

0

»

3

1

Объединение

1

1

1

1

2

Пересечение

1

1

0

1

3

Дополнение

0

0

1

4

Транспозиция

(зеркальное

отображение)

1

1

1

1

5

Произведение

(конкатена­

6

ция)

1

1

1

Итерация

1

1

1

7

Гомоморфизм

1

0

1

1

Определить дополнение языка.

3.

Заданы языки L t = {abbe,

ab,

abec, ас}

и

L% =

{ху, xyz, хг,

хгУ, У2, yzx).

Выполнить операцию умножения этих языков.

4.

Задан

язык L =

{ a n 6 n f n ^ l } .

Выполнить операции транспо­

зиции, умножения, итерации.

5.

Пусть

Vr = {a,

b}, L = {а*ЬЩ1, / > 1 } ,

М =

{а!ЬЩ1,

;>1},

Li =

{а*Ь$ак\1, /, k^l}.

Показать, что язык L 2

= Z.D М

не является

контекстно-свободным, а язык

L 3 — Li — (L f| Щ

является

кон­

текстно-свободным.

6.

Задан язык L =

{ancbn\n^0}.

Выполнить

все

возможные

У4 9-18б1

129