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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

58

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

[ГЛ. ]

и потому Шв(Р). Ясно также, что при любом п

ЛК Л

ипоэтому SR5 неприменим к пустому слову.

6) Отсекающие алгорифмы. Пусть а — некоторая буква, не принадлежащая алфавиту А. Как уже отмеча­ лось, пары слов в алфавите А можно задавать посред­ ством слов вида

PaQ,

где Р, Q е А. В связи с этим иногда оказываются нуж­ ными алгорифмы, выделяющие при таком задании пар первую и вторую компоненты. Эту задачу решают нор­

мальные

алгорифмы ЭТб, 3ll

в алфавите А

[) [а], зада­

ваемые

схемами

 

 

 

 

 

 

 

 

|

ал - * а

(т] <= А)

 

 

 

 

 

 

1

а - > •

 

 

 

 

 

 

 

J т)а - > а

(г) е Л)

 

 

 

 

 

 

1

а - *

 

 

 

 

 

Действительно,

 

 

 

 

 

 

 

 

91в: P a Q H - Я а Ь - Р ,

 

 

 

 

 

 

We: PaQh=aQ Н • Q.

 

 

 

 

Следовательно,

 

 

 

 

 

 

 

 

 

$(/>aQ) = P,

 

 

 

 

 

 

 

«Rl (PaQ)==Q.

 

 

 

 

Отметим,

что

поскольку слова в A U {а}, в

которые

не

входит а, не поддаются алгорифмам

9й,

то

Ш1,

3ll

применимы и к таким словам. Таким образом,

SKg, 5^6

применимы к любым словам

в алфавите A U {а}.

 

7) Алгорифм левого присоединения

слова.

Пусть Р —

произвольное

слово в алфавите А. Рассмотрим нормаль­

ный алгорифм

9^7 в

Л со схемой

 

 

 

 

 

НОРМАЛЬНЫЕ

АЛГОРИФМЫ

 

59

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

 

 

 

 

^ ( Q ) =

PQ.

 

 

Алгорифм 5Ri

(примера 1)

можно рассматривать как

алгорифм левого

присоединения пустого

слова.

 

8) Алгорифм

правого присоединения

слова.

Построе­

ние этого алгорифма несколько сложнее. Пусть

а — не­

которая буква, отличная от всех букв алфавита А. Рас­

смотрим

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

в

алфавите A U {а}

со схемой

 

 

 

 

 

 

(5)

 

 

аг)->т]а

( ц е ^ )

 

 

(6)

 

 

а - *

Р

 

 

 

 

(7)

 

 

—> а

 

 

 

 

Пусть

Q — произвольное слово в

алфавите

А. Сна­

чала

к Q слева приписывается

а (формула (7)):

 

 

 

<:

Q Н aQ.

 

 

 

Затем

а

«бежит»

вправо

по

слову

Q

(группа

формул

(5)),

т. е.

 

 

 

 

 

 

 

 

 

 

«Па: aQHQa,

 

 

 

и, наконец, а заменяется на Р (формула

(6)):

 

Таким

образом,

Я?:

QahQP.

 

 

 

Ki(Q) =

QP,

 

 

 

 

 

 

 

 

 

т. е. Зев присоединяет к любому слову

справа

слово Р.

9)

Обращающий

алгорифм.

Пусть

 

 

(8)

 

 

Р =?= Y1Y2

• • • Y*

 

 

 

— произвольное (непустое) слово в алфавите А. Обра­ щением Р назовем слово Q, записанное теми же бук­ вами, но в обратном порядке, т. е.

Q=r= YftYft-i . . . Yi-

Обращением пустого слова будем считать пустое слово. Обозначим через a, р две различные буквы, не входящие в алфавит Л, и рассмотрим нормальный

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

алгорифм *R9 в

алфавите

A U {ар}

со следующей схе­

мой * ) :

 

 

 

(9)

act - > р

 

 

(10)

р а - * р

 

 

(П)

Р£-£Р

(£б=Л)

(12)

 

 

 

(13)

al^vfit,

(£, t i e

Л)

( И )

—>• а

 

 

и покажем, что Sftg перерабатывает любое слово в алфа­ вите А в его обращение.

Для пустого слова имеем (сначала применяется два раза формула (14), затем формулы (9) и (12))

% : Л Н о Ь а а 1-р Н - Л .

 

Аналогично, для однобуквенного слова

Р = F yi

%• Yi Н «Yi Ь a «Yi

Ь PYi Н Y I P Н • Yi-

Пусть теперь Р — слово

вида (8) с k

2. Так же,

как и раньше, поскольку а

и р не входят

в Р, сначала

применяется формула (14):

%: Р Ь- аР.

Далее, очевидно, применяются формулы группы (13), (формулы (10) — (12) не могут применяться из-за отсут­ ствия буквы р в слове аР, а формула (9) из-за того, что в аР не входит aa) и а «проносит» первую букву слова Р в конец:

%: аР t= Y2Y3 • • • Y*oYi«

Затем снова применяется формула (14):

%: у2у3 • • • YftOYi Н ay2 Y3 • • • Y A O Y I

и а «проносит» в конец букву у2:

CIY2Y3 . . • Yft«Yi И Ys • • • YfeOY2aYi-

*) Здесь используется несколько более сложная, чем раньше, сокращенная запись. Именно, a£r] -*• г|а£ означает группу формул, получаемую всевозможными подстановками вместо £ и Т] любых букв алфавита Л,

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

61

После ряда таких циклов получаем наконец обраще­ ние Р, «разбавленное» буквами а:

%'• ^Иау&ауй-! . . . <XYI.

Обозначим YftaY><-i • • • a Y i через Р а . Очевидно,

 

 

%: аРа

\- ааРа

I - рР а .

Затем

р «бежит»

вправо, уничтожая а (группа формул

(11) и

формула

(Ю)):

 

 

 

P^aH= YfeYfe-i

. . . YiP

Ь-YftYft-i • •• Yi-

Следовательно, 9сэ переработал Р в его обращение, что и требовалось.

В качестве упражнения предлагаем читателю по­ строить удваивающий нормальный алгорифм, т. е. такой нормальный алгорифм 91, что при любом Р

% (Р) — pp.

Приведем в заключение два примера, связанных с на­ туральными числами, — именно, нормальные алгорифмы, складывающие и умножающие натуральные числа. Под натуральными числами мы подразумеваем слова в ал­ фавите {0|} вида 0, 0|, 01 | . . . Пары натуральных чисел задаются как слова вида *)

(15)

 

 

т,

п

 

 

где тип

— натуральные

числа.

 

 

10)

Алгорифм

сложения

натуральных

чисел.

По­

строение этого алгорифма совершенно очевидно: доста­ точно выбросить из слова (15) букву «,» и букву «0», которой начинается т. Схема соответствующего нор­ мального алгорифма SRio (в алфавите {0|}) имеет одну формулу

{,

11) Алгорифм умножения натуральных чисел. Рас­ смотрим нормальный алгорифм Sftn в алфавите {0|, ah)

*) Обращаем внимание читателя на то, что следует различать употребление запятой как пунктуационного знака русского языка и как буквы используемых нами алфавитов.

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