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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

 

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

53

вите А

задается посредством (упорядоченного)

списка

формул

подстановок (как простых, так и заключитель­

ных) в этом алфавите. В качестве исходных данных до­

пускаются произвольные слова в алфавите

А.

Работа

нормального

алгорифма 91 над произвольным

словом

Р

(в

алфавите

А)

описывается

следующим

образом.

 

 

1) Если ни одна из левых частей формул

подстано­

вок

не входит в Р, то процесс применения 21 к Р

закан­

чивается

и

его

результатом

считается

само

слово

Р.

В этом

случае

говорят, что слово Р не поддается алго­

рифму 31.

 

 

 

 

 

 

 

 

2) Если хотя бы одна из левых частей формул под­

становок входит в Р, то отыскиваем самую первую

(в по­

рядке следования в списке)

из таких формул

и

выпол­

няем подстановку правой части этой формулы вместо первого вхождения ее левой части в Р. Если использо­ ванная формула была заключительной, то процесс при­ менения 91 заканчивается и получившееся слово счи­ тается его результатом. В случае простой формулы под­ становки с получившимся словом поступаем так же, как и с Р (ср. рис. 2).

 

 

 

 

Выход

 

 

3

 

j

 

з

Вход

Щ

 

р2 — щ

 

Выход

 

i

/

Pn—BQn

 

г

2

2

 

 

 

Рис. 2. Блок-схема нормального алгорифма.

На рис. 2 б означает либо «•» (заключительная фор­ мула подстановки), либо пустое слово (простая формула подстановки). Блок

Р

Вход

54

 

АЛГОРИФМЫ

И

ППРЕЧИСЛПМЫЕ

МНОЖЕСТВА

 

[ГЛ. 1

работает

следующим

образом: если

Pt не

входит

в по­

ступившее на

вход

слово

Р,

то Р

передается в

(i +

1)-й

блок

(или

на

выход

алгорифма, если i = «); если Pt

вхо­

дит в Р, то выполняется подстановка Q,- вместо первого

вхождения Я,- в

Я

и получившееся слово передается на

выход 2 в случае простой формулы

подстановки

( 6 = г Л )

и на

выход

3

в

случае

заключительной

формулы

( б =

•)•

 

 

 

 

 

 

 

 

 

 

 

 

Таким

образом,

для

полного

задания

нормального

алгорифма необходимо указать алфавит, в котором дей­ ствует этот алгорифм, и выписать список формул под­ становок в этом алфавите. В дальнейшем (следуя М а р ­

к о в у [2]) мы будем

при задании нормальных алгориф­

мов выписывать формулы подстановок друг под другом

(порядок следования

формул, учитываемый в разделе 2)

определения нормального алгорифма, — сверху вниз), объединяя их слева фигурной скобкой (см. п. 4). Полу­ чаемые таким образом фигуры называются схемами нормальных алгорифмов.

Согласно приведенному нами определению примене­

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

к данному слову состоит

в процессе последовательного

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

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

процесса

применения

нормального алгорифма:

1) на некотором этапе получилось слово, не поддаю­

щееся

данному алгорифму

(естественный обрыв);

2)

на

некотором

этапе

применена заключительная

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

Легко,

однако, видеть,

что можно ограничиться нор­

мальными алгорифмами, у которых процесс применения заканчивается лишь заключительным обрывом. В самом деле, если мы присоединим к схеме нормального алго­ рифма 51 снизу формулу «—>•» (с пустой левой и правой частью), то, с одной стороны, получившемуся алгорифму будут поддаваться все слова, а с другой стороны, он бу­ дет вполне эквивалентен 91 относительно их общего ал-

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

55

фавита. Указанный только что алгорифм мы называем замыканием 21 и обозначаем посредством % ' * ) .

4. Прежде чем привести примеры нормальных алго­

рифмов, условимся о

некоторых

обозначениях.

Пусть

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

Р — слово в его

алфавите

и Р поддается

21, т. е. в схеме

21 есть формулы

подстано­

вок с левыми

частями,

входящими

в Р. Тогда

процесс

применения 21 к Р начнется с использования одной из этих формул (именно, самой верхней), в результате чего получится некоторое слово Q. Если использованная фор­ мула подстановки была простой, то мы говорим, что 21 просто переводит Р в Q за один шаг, и пишем 21: Р (— Q. В случае заключительной формулы подстановки мы го­ ворим, что 21 заключительно переводит Р в Q за один шаг, и пишем 21: Р (— • Q.

Вместо

записи

21:

Р0 г- Ри 21: Р, h Р 2 , . . . . Я: Л , - , I - Рп

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

21: Р0

\-Р{

\-Р2 Н

. . . Р„_, h Л,

или

 

 

21: Р 0

Р„,

или даже

 

 

 

 

 

 

Аналогично вместо

записи

 

21: Р 0 Н Р „

 

21: Р, Ь - Р 2

21: Р„_, | - - Р „

будут применяться

записи

 

21:

Р 0

г - Р , г- . . .

/>„_, Г--Р»,

21:

Ро\=^п'Рп>

 

2t:

P o N - ^ -

 

Во всех приводимых ниже примерах мы считаем фи­ ксированным некоторый алфавит А = {aia2 . . . a„}. Упо­ минания об этом алфавите часто опускаются.

*) В качестве полезного упражнения предлагаем читателю до­ казать, что рассмотрение лишь алгорифмов с естественным обры­ вом сужает класс нормальных алгорифмов.

56

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

[ГЛ. 1

1) Тождественный алгорифм. Пусть нормальный ал­ горифм 3li в алфавите А задается схемой

{-*•

Ясно, что для любого слова Р (в алфавите А) 5R,: PhP.

Таким образом, 1 применим к любому слову и всегда

%(Р)^Р-

2)Пустой алгорифм. Определим нормальный алго­ рифм 312 в алфавите А схемой

 

 

 

{->

 

Очевидно,

неприменим

ни к какому слову,

поскольку

при любых Р и п >

О

 

 

 

 

%•

Р\=пР-

 

3) Аннулирующий

алгорифм. Рассмотрим

нормаль­

ный алгорифм 5Яз в алфавите А со схемой

 

'а,->

а2 -»-

 

а„->-

 

 

Пусть Р =?= £i . . . £ь — произвольное

непустое

слово

в алфавите А. Поскольку см

а„ — вое буквы

алфа­

вита

А, то найдется наименьшее i такое, что а,-

входит

в Р.

Пусть / — наименьшее натуральное

число такое, что

а* =

Z,j. Тогда, очевидно, на

первом шаге 5R3 «выбрасы­

вает» £j из Р, т. е.

%: Р Ь £ , . . .

После k таких 'Шагов мы получаем пустое слово, т. е.

%• РЫЛ-

Кроме того, пустое слово не поддается ЭДз. Таким обра­ зом, SR3 перерабатывает любое слово в пустое слово.

При рассмотрении схемы 913 бросается в глаза одно­ родная группа формул, связанных с перечислением всех

букв алфавита. Ясно также,

что изменение

порядка,

в котором перечисляются эти

формулы, никак

не отра-

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

57

зилось бы на результатах работы интересующего нас алгорифма. Сказанное оправдывает применение в по­ добных ситуациях сокращенных записей типа

Здесь первая строка означает группу формул, полу­ чаемую при «пробегании» переменной т| всего алфавита А, причем порядок, в котором выписываются эти фор­ мулы, в данной записи не указывается. Таким образом, схема нормального алгорифма может быть восстановле­ на по сокращенной записи лишь с точностью до порядка расположения некоторых формул. Поэтому сокращенные записи применяются только в тех ситуациях (как, на­ пример, в случае аннулирующего алгорифма), где такая неоднозначность не существенна.

4) Алгорифм, применимый лишь к пустому слову.

Рассмотрим нормальный алгорифм в алфавите А, оп­ ределяемый схемой (в сокращенной записи)

{Г|->Г|

( t ) G 4

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

непустого слова Р и любого

п > О

 

%:

РЫР.

ипоэтому 914 неприменим к Р.

Сдругой стороны, пустое слово не поддается SR4 и, следовательно,

 

9?4 ( Л ) =т= Л .

 

 

5)

Алгорифм, применимый

лишь к

непустым

словам.

Пусть

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

в алфавите

А со

схемой

 

 

 

 

Г ] - > п

(г\е=А)

 

 

Для любого непустого слова Р, очевидно,

%: Р Ь- • Р

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