Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

R' опять берется первая в этом списке подстановка, кото­ рая к нему применима, и она тоже применяется к самому левому вхождению своей левой части; если после конечного числа таких шагов получается слово S, к которому ни одна из этих подстановок уже неприменима, то говорят, что алго­ ритм применим к слову R и перерабатывает его в слово S*.

Нормальные алгоритмы. Алгоритмы для переработки слов в не­ котором алфавите, которые задаются таким образом посредством какой-либо упорядоченной системы ориентированных подстановок, называются нормальными. Теория нормальных алгоритмов, пред­

приведения применим к нему и перерабатывает его в одно

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

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

Пусть, например, даны слова cacb и ЬЬ. Находим при­ веденные слова:

39

первых, заметим, что если дана дедуктивная цепочка, ве­ дущая от какого-либо слова R, не содержащего буквы Ь, к слову 5, также не содержащему этой буквы, то можно из нее извлечь дедуктивную цепочку, ведущую от R к S, но такую, что в промежуточных словах цепочки не встречается буква Ь. Действительно, если во всех словах данной дедуктивной цепочки заменить каждое вхождение буквы b словом асе, то получится последовательность слов, в которой каждые два рядом стоящие слова являются смеж­ ными (в смысле исчисления) или просто одинаковыми. Если удалить теперь лишние повторяющиеся слова (из рядом стоящих), то получится нужная дедуктивная цепочка. В де­ дуктивных цепочках этого типа совсем не участвует подста­ новка b — асе.

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

Если бы имела место эквивалентность хотя бы одной из

40

называется число всех вхождений буквы с, встречающихся правее этого вхождения буквы а. Индексом слова R называет­ ся сумма индексов всех вхождений буквы а*'. Каждая из подстановок аа— Д и сссс— Д не меняет четности индекса слова. Действительно, при подстановке аа вместо пустого слова индекс слова увеличивается на сумму равных между собой индексов этих двух вхождений буквы а, т. е. на чет­ ное число; при замене же вхождения аа пустым словом ин­ декс слова уменьшается на четное число.

При подстановке сссо индексы некоторых вхождений а увеличиваются на четыре, индексы других не изменяются; в целом индекс слова увеличивается на четное число. Ана­ логично при зачеркивании сссс. Подстановка Ь — асе оче­ видным образом не меняет четности индекса слова.

Наконец, покажем, что подстановка са — ассс изменяет четность индекса слова. Для этого сравним слова PcaQ и PacccQ; индекс каждого вхождения а в часть Р слова R из­ меняется ровно на 2, а индекс вхождения а. в Q не из­ меняется. Чго же касается индекса единственного вхожде­ ния а между Р и Q, то он изменяется в точности на 3. В це­ лом индекс слова изменяется на нечетное число. Оба слова ас и ассс имеют индексы одной и той же четности; поэтому, если они эквивалентны, то в соответствующей дедуктивной цепочке (можно считать, что в ней буква Ь не встречается, см. выше) может быть лишь четное число подстановок са — ассс.

Однако такое предположение приводит к противоре­ чию, как видно из следующих рассуждений. Каждое при­ менение подстановки са — ассс меняет число вхождений бук­ вы с на 2, поэтому четное число ее применений меняет чис­ ло вхождений буквы с на число, кратное четырем. Очевидно,

числа. Подведя итог всему сказанному, мы должны заклю­ чить, что если ас ~ ассс, то количества вхождений буквы с в них отличаются на число, кратное четырем, чего на самом

*) Например, в слове acbca первое слева вхождение буквы о имеет индекс 2; второе же слева вхождение буквы а имеет индекс О (правее нет вхождений буквы с). Индекс слова — 2.

41

деле Нет. Итак, слова ас и йссс неэквивалентны. Вместе с тем мы завершили обоснование предложенного алгоритма.

4.5. Самосовмещения квадрата. Приведенное в примере 4 подробное решение проблемы слов для конкретного ассо­ циативного исчисления во многом характеризует понятия и методы, возникающие и при исследовании проблемы слов для других исчислений. Нам остается еще пояснить содер­ жательный смысл проблемы слов и ее значение в современ­ ной алгебре. Это удобно сделать не конкретном примере.

Вертикальная ось

Левая диагональ

Горизонтальная ось

Правая диагональ

Л

Я Сг

Рис. 9.

Возьмем какой-нибудь квадрат (рис. 9, I). Рассмотрим следующие три его самосовмещения, т. е. преобразования, которые переводят квадрат в самого себя:

1)симметрия (зеркальное отображение) относительно вертикальной оси, проходящей через центр квадрата О;

2)симметрия относительно горизонтальной оси, про­ ходящей через центр квадрата О;

3)вращение по часовой стрелке на 90° вокруг центра О. Эти преобразования будем называть элементарными и

обозначать буквами а, Ь, с соответственно. На рис. 9 ( I I I — IV—V) показано, как изменяется расположение вершин квадрата (II) при каждом из элементарных преобразований.

42

Заметим, что в результате последовательного осуществле­ ния каких бы то ни было двух или нескольких самосовме­ щений квадрата происходит также самосовмещение квадра­ та. Будем придерживаться общепринятого определения, со­ гласно которому умножить два заданных преобразования (в частности, два самосовмещения квадрата), — значит последовательно произвести их одно за другим. Условимся еще для операции умножения преобразований сохранить обычные обозначения, а также термин произведение для ре­ зультирующего преобразования. Например, произведение

ссесть результат двух последовательных вращений по 90°,

т.е. вращение на 180°; произведение, ас — результат сим­ метрии относительной вертикальной оси с последующим поворотом на 90° — равносильно симметрии относительно левой диагонали. Произведение же (ас) [сс) двух предыдущих произведений равносильно симметрии относительно правой диагонали (см. рис. 9, I).

пример, (ас) (сс) и (((ас)с)с) дают одно и то же самосовмеще­ ние квадрата—симметрию относительно левой диагонали.

Объектом наших последующих рассмотрений будет со­ вокупность Q, состоящая из элементарных преобразований а, Ь, с и всех самосовмещений квадрата, которые могут быть представлены как произведения конечного (но произвольного) числа элементарных преобразований. Бла­ годаря ассоциативности умножения при символической записи элементов из Q, можно опустить скобки и ограничить­ ся записью в соответствующем порядке букв, изобра­ жающих соответствующие элементарные самосовмещения, например abb, cabb, ассс и т. д. Это означает, что всякое про­ изведение изобразится в виде слова в алфавите {а, Ь, с).

Из ассоциативности умножения вытекает также, что если к слову Р приписать справа слово Q так, чтобы полу­ чилось одно слово PQ, то оно будет изображать произведе­ ние самосовмещений, изображенных словами Р и Q соот­ ветственно; например, слово abccab изображает произведе­ ние совмещений, изображаемых словами abc и cab.

43