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

Осталось только уничтожить символы # и =,после чего остановиться.Теперь отметим, что в НАМ, реализующем такое копирование, важен взаимный порядок расположения формул (Aξ→ξA, Bξ→ξB, A→a и B→b), которыепереносят символы A и B в конец и там восстанавливают символы a и b, иформулами (#a→a#A и #b→b#B), которые «вводят в игру» символы A и B.Поскольку последняя пара формул должна срабатывать только после того, каксимвол A или B будет полностью перенесён в конец и заменён на a или b, то этапара формулы должна располагаться в НАМ ниже всех первых формул.И ещё один момент. В этом НАМ используются два спецзнака * и #, первый из которых нужен для приписывания символа = справа к входному слову, авторой – для указания, какой символ слова должен копироваться следующим.Как ввести эти спецзнаки? Отметим, что использовать для этого две формулы→* и →# нельзя, т.к. первая из них будет блокировать доступ ко второй.

Обаэтих спецзнака надо вводить сразу одной формулой →#* . При этом надо учи30тывать, что формулы с * должны применяться самыми первыми, поэтому онидолжны располагаться в начале НАМ. Формулы же с #, A и B должны располагаться ниже, чтобы они работали только после того, как исчезнет * и появитсясимвол =.С учётом всего сказанного получаем следующий НАМ:(1)⎧ *a → a*⎪ *b → b *( 2)⎪* →=(3)⎪( 4)⎪ Aa → aA→(AbbA5)⎪⎪ A = → = A ( 6)⎪ A →a(7 )⎪→(8)BaaB⎨⎪ Bb → bB(9 )⎪ B = → = B (10)⎪(11)⎪ B →b⎪ # a → a # A (12)⎪ # b → b# B (13)⎪ #= a(14)⎪→#*(15)⎩Здесь формулы (1)–(3) «перегоняют» звёздочку в конец входного слова изаменяют её на символ =.

Формулы (4)–(7) перегоняют символ A в конец слова,после чего заменяют на a. Формулы (8)–(11) делают то же самое с B и b.Формулы (12 и (13) «вводят в игру» символы A и B, соответствующие томусимволу входного слова, который должен быть скопирован следующим.Формула (14) применяется только тогда, когда справа от # нет ни a, ни b, т.е.когда полностью просмотрено всё входное слово.

И, наконец, формула (15)вводит сразу два спецзнака # и *.Проверим данный алгоритм на двух входных словах – на пустом и на abb:15314<пустое слово> → #* → #= a151,23(т.е. получили <пустое слово><пустое слово>)124-6812abb → #*abb ⇒ #abb* → #abb= → a#Abb= ⇒ a#bb=A → a#bb=a →128-1011128-1011→ ab#Bb= ⇒ ab#b=aB → ab#b=ab → abb#B=ab ⇒ abb#=abB →1114→ abb#=abb a abbabbДругое решениеПриведём ещё одно решение задачи удвоения слова, в которомпредлагается выполнить следующие действия.1.

Сначала за каждой (малой) буквой входного слова вставляем её двойник– соответствующую большую букву. Для этого приписываем слева к словуспецзнак *, а затем переносим его через каждую малую букву так, чтобы слева31от него остались эта буква и её двойник. В конце слова заменяем * на новыйспецзнак #, который нам ещё понадобится:abb → *abb → aA*bb → aAbB*b → aAbBbB* → aAbBbB#2. В получившемся слове переставляем малые и большие буквы так, чтобыслева оказались все малые буквы, а справа – все большие, сохраняя при этомисходный взаимный порядок как среди малых, так и среди больших букв:aAbBbB# → … → abbABB#3.

Как видно, справа мы получили копию входного слова, но записаннуюбольшими буквами. Осталось только заменить их на малые буквы. Вот здесь-тои понадобится спецзнак #: будем перемещать его влево через каждую большуюбукву с заменой её на малую. Когда слева от # уже не окажется большой буквы,надо уничтожить # и остановиться:abbABB# → abbAB#b → abbA#bb → abb#abb a abbabbВсе указанные действия описываются в виде следующего НАМ:⎧ *a⎪ *b⎪*⎪⎪ Aa⎪ Ab⎪⎨ Ba⎪ Bb⎪ A#⎪⎪ B#⎪ #⎪⎩→ aA *→ bB *→#→ aA→ bA→ aB→ bB→ #a→ #ba→*2.3 Задачи для самостоятельного решенияЗамечания:1) В задачах рассматриваются только целые неотрицательные числа, если несказано иное.2) Под «единичной» системой счисления понимается запись неотрицательногоцелого числа с помощью палочек – должно быть выписано столько палочек,какова величина числа; например: 2→ | | , 5 → | | | | | , 0 → <пустое слово>.2.1A={f,h,p}.

В слове P заменить все пары ph на f.2.2A={f,h,p}. В слове P заменить на f только первую пару ph, если такая есть.2.3A={a,b,c}. Приписать слово bac слева к слову P.2.4A={a,b,c}. Заменить слово P на пустое слово, т.е. удалить из P все символы.2.5A={a,b,c}.

Заменить любое входное слово на слово a.2.6Выписать НАМ, не меняющий входное слово (при любом алфавите A).322.7 A={ | }. Считая слово P записью числа в единичной системе счисления,получить остаток от деления этого числа на 2, т.е. получить слово из однойпалочки, если число нечётно, или пустое слово, если число чётно.2.8 A={ | }. Считая слово P записью положительного числа в единичнойсистеме счисления, уменьшить это число на 1.2.9 A={ | }. Считая слово P записью числа в единичной системе счисления,увеличить это число на 2.2.10 A={0,1,2}. Считая слово P записью числа в троичной системе счисления,получить остаток от деления этого числа на 2, т.е.

получить слово 1, если числонечётно, или слово 0, если число чётно. (Замечание: в чётном троичном числедолжно быть чётное количество цифр 1.)2.11 A={a,b,c}. Определить, входит ли символ a в слово P. Ответ (выходноеслово): слово a, если входит, или пустое слово, если не входит.2.12 A={a,b}. Если в слово P входит больше символов a, чем символов b, то вкачестве ответа выдать слово из одного символа a, если в P равное количество aи b, то в качестве ответа выдать пустое слово, а иначе выдать ответ b.2.13 A={0,1,2,3}. Преобразовать слово P так, чтобы сначала шли все чётныецифры (0 и 2), а затем – все нечётные.2.14 A={a,b,c}. Преобразовать слово P так, чтобы сначала шли все символы a,затем – все символы b и в конце – все символы c.2.15 A={a,b,c}.

Определить, из скольких различных символов составлено словоP; ответ получить в единичной системе счисления (например: acaac → | | ).2.16 A={a,b,c}. В непустом слове P удвоить первый символ, т.е. приписать этотсимвол слева к P.2.17 A={a,b,c}. За первым символом непустого слова P вставить символ c.2.18 A={a,b,c}. Из слова P удалить второй символ, если такой есть.2.19 A={a,b,c}. Если в слове P не менее двух символов, то переставить двапервых символа.2.20 A={0,1,2}.

Считая непустое слово P записью троичного числа, удалить изэтой записи все незначащие нули.2.21 A={a,b,c}. Приписать слово abc справа к слову P.2.22 A={a,b,c}. Удалить из непустого слова P его последний символ.2.23 A={0,1}. Считая непустое слово P записью числа в двоичной системе,получить двоичное число, равное учетверённому числу P (например: 101 → 10100).2.24 A={0,1}. Считая непустое слово P записью числа в двоичной системе,получить двоичное число, равное неполному частному от деления числа P на 2(например: 1011 → 101).2.25 A={a,b}. В слове P все символы a заменить на b, а все (прежние) символыb – на a.332.26 A={a,b,c}. Удвоить каждый символ в слове P (например: bacb → bbaaccbb).2.27 A={a,b}. Приписать справа к слову P столько палочек, сколько всегосимволов входит в P (например: babb → babb||||).2.28 A={a,b}.

Пусть слово P имеет чётную длину (0, 2, 4, …). Удалить правуюполовину этого слова. (Рекомендация: использовать решение предыдущей задачи.)2.29 A={a,b}. Пусть длина слова P кратна 3. Удалить правую треть этого слова.2.30 A={a,b}. Приписать справа к слову P столько палочек, со скольких подрядидущих символов a начинается это слово (например: aababa → aababa| | ).2.31 A={a,b,c}. Удалить из слова P второе вхождение символа a, если такое есть.2.32 A={a,b,c}. Удалить из слова P третье вхождение символа a, если такое есть.2.33 A={a,b,c}.

Оставить в слове P только первое вхождение символа a, еслитакое есть.2.34 A={a,b,c}. В непустом слове P оставить только последний символ.2.35 A={a,b,c}. Из всех вхождений символа a в слово P оставить только последнее вхождение, если такое есть.2.36 A={a,b,c}. Если слово P начинается с символа a, то заменить P на пустоеслово, а иначе P не менять.2.37 A={a,b}. Если слово P содержит одновременно символы a и b, то заменитьP на пустое слово.2.38 A={a,b,c}. Если буквы в непустом слове P не упорядочены по алфавиту, тозаменить P на пустое слово, а иначе P не менять.2.39 A={a,b,c}. Если P отлично от слова abaca, то заменить его на пустое слово.2.40 A={0,1}.

Считая непустое слово P записью двоичного числа, определить,является ли это число степенью 2 (1, 2, 4, …). Ответ: слово 1, если является, илислово 0 иначе.2.41 A={0,1,2,3}. Считая непустое слово P записью четверичного числа, проверить, чётно оно или нет. Ответ: слово 0, если чётно, и слово 1 иначе.2.42 A={0,1,2,3}. Считая непустое слово P записью четверичного числа,получить остаток от деления этого числа на 4.2.43 A={0,1}. Считая непустое слово P записью двоичного числа, получить этоже число, но в четверичной системе. (Замечание: учесть, что в двоичном числеможет быть нечётное количество цифр.)2.44 A={0,1,2}.