книги из ГПНТБ / Кушнер, Б. А. Лекции по конструктивному математическому анализу

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

В качестве другого примера рассмотрим вхождения пу­ стого слова в слово «ба». Таких вхождений имеется три: ааба, бааа и бааа. Вообще, число вхождений пустого слова в слово длины п равно п -f- 1.

Вхождение (3) слова Р в слово Q будем называть первым вхождением Р в Q, если длина левого крыла любого вхождения Р в Q не меньше длины Ri. Напри­ мер, вхождение (4) является первым вхождением слова

жит та идея, что любой алгорифмический процесс над словами может быть сведен к выполнению локальных преобразований слов, т. е. к замене вхождений одних слов в другие некоторыми третьими словами. При этом в описании алгорифма должен быть указан список раз­ решенных преобразований такого типа, т. е. должно быть указано, какие слова и на какие можно заменять. Кроме того, поскольку одни слова могут входить в другие не­ сколькими различными способами, нужно уточнить, вме­ сто каких именно вхождений следует выполнять подста­ новки из упомянутого только что списка. Наконец, для однозначной определенности процесса применения алго­ рифма надлежит как-то фиксировать очередность, в ко­ торой выполняются разрешенные подстановки. Опреде­ ление нормального алгорифма, к которому мы перехо­ дим, предлагает некоторый естественный вариант такого рода уточнений.

называются левой и правой частью соответствующей формулы подстановки). Нормальный алгорифм в алфа-

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

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

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

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

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

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

{-*•

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

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

%(Р)^Р-

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

'а,->

а2 -»-

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

%: Р Ь £ , . . .

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

%• РЫЛ-

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

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

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

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

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

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

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

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

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

%: Р Ь- • Р

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

ЛК Л

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

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

PaQ,

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

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

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

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

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

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

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

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

применяется формула (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] -*• г|а£ означает группу формул, получаемую всевозможными подстановками вместо £ и Т] любых букв алфавита Л,