Файл: Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 147

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

72

АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

[ГЛ. I

т.е. схему некоторого алгорифма (S, удовлетворяющего

(44)(мы отвлекаемся сейчас от неоднозначности опи­ санной выше схемы (S, связанной с выбором букв-

двойников,

букв а, р и порядком

формул

в

группах

(30) —(35),

(37) — (38)). Этот алгорифм мы

будем

ино­

гда обозначать посредством (53 о 21).

 

 

 

 

Чтобы проиллюстрировать применение теоремы ком­

позиции, вернемся к отсекающим

алгорифмам

(при­

мер 6) п. 4). Пусть, как и в п. 4, Л—некоторый

алфавит,

а — б у к в а ,

не принадлежащая этому

алфавиту.

Мы не­

сколько изменим схемы отсекающих алгорифмов, доба­

вив

в схему первого из них формулу оса —• а. Именно,

обозначим через В1,

В2

нормальные алгорифмы в A U {а}

со

схемами

 

 

 

 

 

 

 

f

аг)

 

а

(г) <= А

[} {а})

 

 

1

а -* •

 

 

 

 

(

Г)а

 

а

(т) <= Л)

 

 

Пусть Р — слово вида

 

 

(45)

 

 

Р

 

PtaP2a

...

aPk,

где все Р{

(I ^ i ^

k)

— слова в .4.

 

Легко

видеть, что

 

 

 

 

 

 

В1(Р)~Ри

 

 

 

 

 

В2(Р)

= Р2а ...

aPk.

Обозначим через

Вп(п^1)

нормальные алгорифмы

 

 

 

 

 

В\ =

Вг,

 

 

 

 

 

 

В\ =

(В2оВг),

В2п+1 = (В2оВ1)

и рассмотрим нормальные алгорифмы Вп:

В, = В\

Bn+i = {BloB2n).

 

 

НОРМАЛЬНЫЕ

АЛГОРИФМЫ

 

73

Ясно, что для любого

слова вида

(45)

с k ^

п

 

 

В я (Р)=рЯ„ .

 

 

 

Таким

образом, Вп

«выбирает»

п-ю

компоненту

а-кортежа длины, не меньшей п.

 

 

 

2) Теорема

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

Очень

часто встречаются

ситуации,

когда

интересующий нас

результат

слагается

из нескольких частей, получаемых при помощи различ­ ных алгорифмов. В случае словарных алгорифмов можно

сформулировать следующее

предписание:

применить

к данному слову Р алгорифмы

21 и 23, затем к резуль­

тату работы 91 приписать справа результат,

полученный

посредством 93. Алгорифм, возникающий согласно этому

предписанию из 91 и 93, естественно

назвать

объедине­

нием 91 и 93. Имеет

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

теорема

объедине­

ния нормальных

алгорифмов.

 

 

 

 

4]). Каковы

бы

 

Т е о р е м а

5

( М а р к о в

[2; гл. 3,

§

ни

были

 

нормальные

алгорифмы

91

и

23 над

алфави­

том А,

может

быть

построен

 

нормальный

алгорифм

S

над

А такой, что при

любом слове

Р в

А

 

 

 

(46)

 

 

 

£ (Р) ~

21 (Р) 23 (Р).

 

 

 

 

 

Почти очевиден следующий вариант теоремы объеди­

нения.

 

 

 

Каковы

бы

ни были

нормальные

алго­

 

Т е о р е м а

6.

рифмы

21

и 23

над

алфавитом

А

и буква

а, можно

по­

строить нормальный

алгорифм

 

(5

над

A U {а} такой, что

 

 

 

 

 

6 (Р) ~

21 (Р) а23 (Р)

 

 

 

 

при

любом

слове

Р в алфавите

А.

 

 

 

 

 

 

Для

доказательства теоремы

6 достаточно

два

раза

применить теорему 5, используя при этом нормальный

алгорифм

Ф а , перерабатывающий всякое

слово Р в ал­

фавите А в букву а * ) .

 

 

Теоремы 5—6 очевидным

образом распространяются

на случай

объединения нескольких нормальных алгориф­

мов. Их

особенно удобно

использовать

(в сочетании

*) 2 ) а легко построить как композицию аннулирующего алго­ рифма (пример 3) п. 4) и алгорифма (пример 7) п. 4). Мы также предлагаем читателю в качестве простого упражнения по­ строить алгорифм 3 ) а непосредственно.

74 АЛГОРИФМЫ И ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА [ГЛ. 1

с теоремой композиции) тогда, когда результаты работы

нескольких алгорифмов, объединенные (как

правило,

с использованием разделительной буквы) в

систему,

сами должны рассматриваться как исходные данные не­ которого нового алгорифма.

Ясно, что алгорифм (5, построенный согласно тео­ реме 5, применим к тем и только тем словам в Р, к ко­

торым применимы оба алгорифма 21

и 53, т. е. имеет

место

 

2. Каковы

бы

ни были

нормальные

ал­

С л е д с т в и е

горифмы

<& и 33 над алфавитом

А, можно

построить

нор­

мальный

алгорифм

над А,

применимый

к

тем и только

тем словам в А, к которым

применимы

оба

алгорифма

Ш

и93.

Вкачестве примера применения теорем композиции и объединения построим алгорифм Ф, распознающий гра­ фическое равенство слов в алфавите А. Пусть а — бук­ ва, не принадлежащая А. Мы хотим, чтобы для любых слов Р и Q в А выполнялось

IS) (PaQ)

и

 

 

 

 

 

 

 

 

(47)

 

2)(P<xQ)= Д =

P ~ Q .

 

 

 

 

Рассмотрим нормальный алгорифм ®i со схемой

 

 

 

I т)аг)

а

(г) е

А)

 

 

 

 

 

1 а-»-

 

 

 

 

 

 

Для каждого слова Р обозначим через Р его обра­

щение

(см. пример 9)

п. 4). Легко

видеть, что

для

лю­

бого слова PaQ

ID, (PaQ)

 

 

 

 

и

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(48)

£ , ( P a Q ) = A

^ Q

= P.

 

 

 

 

По теореме композиции построим алгорифм 3)2 так,

НТО

®2(PaQ)~%(B2(PaQ)),

 

 

 

 

 

 

 

 

 

 

где

SR9

— обращающий

алгорифм

(пример

9)

п.

4),

а

В2 — построенный

выше

«высекающий»

алгорифм.

$ и

НОРМАЛЬНЫЕ АЛГОРИФМЫ

75

Очевидно,

 

 

 

 

(49)

 

2>2 (PaQ) ~ Q.

 

Построим далее алгорифм $53 по теореме объедине­

ния так, что

 

 

 

 

 

£>3 (PaQ) ~

В, (PaQ) a© 2

(PaQ),

 

где Bi — построенный

выше

«высекающий»

алгорифм.

Ввиду

(49)

 

 

 

 

(50)

©з (PaQ) ~

PaQ.

 

 

Наконец, по теореме композиции строим алгорифм 35

так, что

 

 

 

 

 

35 (PaQ) ~ 35, (353(PaQ)).

 

Ввиду (48) для 35 выполняется (47), что и требова­

лось.

 

 

 

 

 

3)

Т е о р е м а р а з в е т в л е н и я .

Иногда

приходит­

ся рассматривать предписания следующего типа (рис. 4): для данного исходного слова Р проверить, удовлетво­

ряет

ли

оно

данному

условию бФ; если Р

удовлетво­

ряет

si, то

применить к Р алгорифм

91, в

противном

 

 

 

ПроЗсрна

 

 

 

 

 

 

1/шбия с#

 

 

 

 

Рис. 4. Разветвление нормальных алгорифмов.

случае применить к Р

алгорифм 93. Ясно, что такое пред­

писание определяет

алгорифм

в том случае,

когда усло­

вие si разрешимо,

т. е. когда

мы располагаем алгориф­

мом,

применимым

к любому слову Р и аннулирующим

Р тогда

и только

тогда, когда Р удовлетворяет усло­

вию

si*).

Возможность оформления

сформулирован­

ного

предписания

в

виде

нормального

алгорифма

(при

условии, что

91, 93 и алгорифм,

«разрешающий»

*) Мы говорим, что алгорифм аннулирует слово Р, если он перерабатывает Р в пустое слово.

Смотрите также файлы