В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая - Машина Тьюринга и алгоритмы Маркова. Решение задач, страница 6

Как приписать * слева к входному слову и какуничтожить спецзнак с остановом, мы уже знаем по предыдущему примеру, авот «перепрыгивание» звёздочки реализуется с помощью формул вида *α→βγ*,где α – четверичная цифра, а βγ – соответствующая ей пара двоичных цифр.Итого, получаем следующий алгоритм перевода чисел из четверичнойсистемы в двоичную:⎧ * 0 → 00 * (1)⎪ *1 → 01* (2)⎪⎪ * 2 → 10 * (3)⎨ * 3 → 11* (4)⎪(5)⎪* a⎪⎩ → *( 6)Проверим этот НАМ на входном слове 0123:6123450123 → *0123 → 00*123 → 0001*23 → 000110*3 → 00011011* a 00011011Пример 5 (перемещение спецзнака)А={a,b}.

Требуется приписать символ a к концу слова Р.Например: bbab → bbabaРешение.Прежде всего напомним, что формула →a приписывает символ a слева кслову P, а не справа. Чтобы приписать a справа, надо сначала пометить конецслова. Для этого воспользуемся спецзнаком, который поместим в конец P, азатем заменим его на a:P → … → P* a PaНо как поместить спецзнак в конец слова? Делается это так: сначаласпецзнак * приписываем слева к слову P, а затем «перегоняем» звёздочку черезвсе буквы слова:bbab → *bbab → b*bab → bb*ab → bba*b → bbab*А как сделать такой перегон? Нетрудно заметить, что «перепрыгивание» звёздочки через какой-то символ ξ – это замена пары *ξ на пару ξ*, которая реализуется формулой *ξ→ξ*.С учётом всего сказанного получаем следующий НАМ:⎧ *a → a*⎪ *b → b*⎨ * aa⎪→*⎩Отметим, что при пустом входном слове этот НАМ сначала введёт звёздочку, а затем тут же заменит её на символ a и остановится.26Пример 6 (смена спецзнака)А={a,b}.

В слове Р заменить на aa последнее вхождение символа a, если такое есть.Например: bababb → babaabbРешение.Удвоение символа a реализуется формулой a a aa. Но чтобы она применялась не к первому вхождению символа a, а к последнему, надо поставить, скажем, справа от последнего символа a спецзнак * и применить формулу a* a aa.Теперь посмотрим, как поместить * рядом с последним вхождением символа a.

Поскольку последнее вхождение – это первое вхождение от конца, топредлагается сначала приписать * слева к слову P, затем перегнать * в конецслова (это мы уже умеем делать), а далее перегнать * справа налево через символы b до ближайшего символа a. Кроме того, надо учесть, что в Р может и небыть символа a; поэтому, если звёздочка снова достигнет начала слова, её надоуничтожить и остановиться.Реализуем эту идею в виде следующего НАМ:⎧ * a → a * (1)⎪ * b → b * ( 2)⎪⎪ b * → * b (3)⎨ a * a aa (4)⎪(5)⎪* a⎪⎩→*( 6)Здесь формула (6) приписывает * слева к входному слову P, формулы (1) и (2)перегоняют * в конец P, после чего формула (3) перемещает * справа налевочерез все b в конце слова до ближайшего, т.е.

последнего, символа a, и, наконец,формула (4) заменяет этот символ на aa и останавливает алгоритм. Формула же(5) нужна для входных слов, в которые не входит a.Проверим этот алгоритм на входном слове bababb (двойная стрелкаозначает несколько шагов применения формул (1) и (2)):61,23232bababb → *bababb ⇒ bababb* → babab*b → bababb* → babab*b → …Как видно, вместо того, чтобы двигаться справа влево до ближайшегосимвола a, звёздочка начала «прыгать» вокруг последнего символа слова.Почему? Дело в том, что формулы (1) и (2), перегоняющие * вправо, мешаютформуле (3), перегоняющей * влево.

Отметим, что перестановка этих формул непоможет, т.к. тогда * начнёт «плясать» вокруг первого символа входного слова.Что делать?Ошибка произошла из-за того, что мы используем спецзнак * в двухразных целях – как для движения вправо, так и для движения влево. Так вот,чтобы этой ошибки не было, надо просто ввести еще один спецзнак, скажем #,распределив между этими спецзнаками обязанности: пусть * движется вправо, а# – влево.

Появиться же спецзнак # должен тогда, когда * дойдет до концаслова, т.е. когда справа от * не окажется других символов. Такая замена27спецзнака «исключит из игры» все формулы со звёздочкой в левой части,поэтому они уже не будут мешать формулам со спецзнаком #.Если так и сделать, то получим следующий НАМ:⎧ * a → a * (1)⎪ * b → b * ( 2)⎪* →#(3)⎪⎨ b # → # b ( 4)⎪ a # a aa (5)⎪ # a( 6)⎪*(7)→⎩Проверим этот алгоритм на прежнем входном слове:7bababb → *bababb1,2⇒344bababb* → bababb# → babab#b → baba#bb5ababaabbЕсли же во входное слово не входит символ a, тогда имеем:7223446bb → *bb → b*b → bb* → bb# → b#b → #bb a bbПример 7 (перенос символа через слово)А={a,b}. Перенести в конец непустого слова Р его первый символ.

Пустое словоне менять.Например: bbaba → bababРешение.Для решения этой задачи предлагается выполнить следующие действия.1. Помечаем первый символ слова P спецзнаком *.2. Заменяем * и этот символ на новый символ: a на A, b на B. Этим мыфактически вводим два новых спецзнака A и B, которые нужны, чтобы отличитьпервый символ слова от остальных символов при его переносе в конец слова.3. Перегоняем новый символ A или B через все символы слова P в его конец.Такое перемещение реализуется аналогично перегону звёздочки – с помощьюформул вида Aξ→ξA и Bξ→ξB4. Наконец, заменяем A или B в конце слова на прежний символ (A на a, B наb) и останавливаем алгоритм.Все эти действия реализуются в виде следующего НАМ:(1)⎧ *a → A⎪ *b → B( 2)⎪ Aa → aA (3)⎪⎪ Ab → bA (4)⎪ Ba → aB (5)⎨ Bb → bB (6)⎪(7 )⎪ A aa(8)⎪ B ab⎪ * a(9 )⎪*(10)→⎩28Здесь формулы (1) и (2) заменяют первый символ слова (вместе с *) на Аили В.

Формулы (3)–(6) перегоняют А и В в конец слова. Формулы (7) и (8)применяются только тогда, когда А и В окажутся в конце слова (когда за нимиуже нет символов), и восстанавливают исходный вид первого символа. Формула(9) нужна на случай пустого входного слова. Формула же (10) ставит спецзнак *перед первым символом.Проверим этот алгоритм на входном слове baba и на входном слове изодного символа:10265658bbaba → *bbaba → Bbaba → bBaba → baBba → babBa → babaB a babab1017a → *a → A a aДругое решениеОтметим, что в этом НАМ можно уменьшить число формул, если невводить новые символы A и B, а использовать вместо них пары *a и *b. Этопозволит исключить из НАМ формулы (1) и (2), которые вводят символы A и B,и формулы (7) и (8), которые восстанавливают первый символ. Что же касается«перепрыгивания» этих пар через какой-то символ ξ, то оно реализуетсяформулами вида *aξ→ξ*a и *bξ→ξ*b.

При этом никакой путаницы междупервым символом слова и остальными символами не будет, т.к. только передпервым символом находится звёздочка.Итак, возможен и следующий НАМ, решающий нашу задачу:⎧ * aa → a * a (1)⎪ * ab → b * a (2)⎪⎪ * ba → a * b (3)⎨ * bb → b * b (4)⎪(5)⎪ * a⎪⎩( 6)→*Проверим этот алгоритм на прежнем входном слове bbaba:643435bbaba → *bbaba → b*baba → ba*bba → bab*ba → baba*b a bababПример 8 (использование нескольких спецзнаков)А={a,b}. Удвоить слово Р, т.е. приписать к P (слева или справа) его копию.Например: abb → abbabbРешение.Предлагается следующий план решения задачи:1.

Приписываем к концу слова Р символ =, справа от которого будем строитькопию P.2. Просматриваем по очереди все символы слова Р и, не уничтожая их,переносим копию каждого символа в конец.293. Удаляем символ =, который отделял слово P от его копии, и останавливаемалгоритм.Теперь уточним этот план.Как приписать некоторый символ к концу слова, мы уже знаем: надосначала приписать слева к слову какой-то спецзнак, скажем *, затем перегнатьего направо через все символы слова и в конце, когда за * не окажется никакогосимвола, заменить на символ =:abb → *abb → a*bb → ab*b → abb* → abb=Из предыдущего примера мы также знаем, как переносить символы слова вконец слова.

Только теперь сами символы уничтожать уже не надо. Поэтомупоступаем так: если надо скопировать символ a, то порождаем за ним новыйсимвол A (заменяем a на aA), после чего этот символ A переставляем с каждымпоследующим символом (в том числе и с символом =), перенося тем самым A вконец слова, где и заменяем на a:abb= → aAbb= → abAb= → abbA= → abb=A → abb=aАналогично копируются и символы b.Главный вопрос здесь: как узнать, какой именно символ исходного словамы только что скопировали и какой символ надо копировать следующим? Дляэтого используем стандартный приём со спецзнаком – будем помечать новымспецзнаком # тот символ, который должен копироваться следующим (вначалеэто первый символ входного слова):#abb= → a#Abb= → a#bAb= → a#bbA= → a#bb=A → a#bb=aКак только копия очередного символа окажется в конце, спецзнак # должен«запустить» процесс копирования следующего символа:a#bb=a → ab#Bb=a → ab#bB=a → ab#b=Ba → ab#b=aB → ab#b=ab →→ abb#B=ab → abb#=Bab → abb#=aBb → abb#=abB → abb#=abbКогда справа от спецзнака # окажется символ =, это будет означать, что входноеслово полностью скопировано.