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

Считая непустое слово P записью троичного числа, увеличитьэто число на 1.2.45 A={0,1,2}. Считая непустое слово P записью положительного троичногочисла, уменьшить это число на 1.2.46 A={ | }. Считая слово P записью числа в единичной системе счисления,получить запись этого числа в троичной системе. (Рекомендация: следует в34цикле удалять из «единичного» числа по палочке и каждый раз прибавлять 1 ктроичному числу, которое вначале положить равным 0.)2.47 A={0,1,2}.

Считая непустое слово P записью числа в троичной системе,получить запись этого числа в единичной системе.2.48 A={a,b,c}. Определить, входит ли первый символ непустого слова P ещёраз в это слово. Ответ: слово a, если входит, или пустое слово иначе.2.49 A={a,b}. Перенести первый символ непустого слова P в конец слова.2.50 A={a,b}. Перенести последний символ непустого слова P в начало слова.2.51 A={a,b}.

В непустом слове P переставить первый и последний символы.2.52 A={a,b}. Если в непустом слове P совпадают первый и последнийсимволы, то удалить оба этих символа, а иначе слово не менять.2.53 A={a,b}. Определить, является ли слово P палиндромом (перевёртышем,симметричным словом). Ответ: слово a, если является, или пустое слово иначе.2.54 A={a,b}. Пусть слово P имеет нечётную длину. Удалить из него среднийсимвол.2.55 Пусть слово P имеет следующий вид:|{| ... | ⊗ |{| ...

|nmгде ⊗ – один из знаков +, –, ×, /, ÷, ↑ или ↓, слева от которого указано n палочек, асправа – m палочек. Реализовать соответствующую операцию в единичной системе счисления (в качестве ответа выдать слово, указанное справа от стрелки):а) сложение: |{| ... | + |{| ... | → |{| ... | (n≥0, m≥0)nn+ mmб) вычитание: |{| ... | − |{| ... | → |{| ... | (n≥m≥0)nn−mm| ... | × |{| ...

| → |{| ... | (n≥0, m≥0)в) умножение: |{nn×mm| ... | / |{| ... | → |{| ... | (n≥0, m>0, k=n div m)г) деление нацело: |{nmk| ... | ÷ |{| ... | → |{| ... | (n≥0, m>0, k=n mod m)д) взятие остатка: |{nmkе) максимум: |{| ... | ↑ |{| ... | → |{| ... | (n≥0, m≥0, k=max(n,m))nmkж) минимум: |{| ... | ↓ |{| ... | → |{| ... | (n≥0, m≥0, k=min(n,m))nmk2.56 A={ | }. Считая слово P записью числа в единичной системе, определить,является ли это число степенью 3 (1, 3, 9, 27, …).

Ответ: пустое слово, еслиявляется, или слово из одной палочки иначе.2.57 A={ | }. Считая слово P записью числа n в единичной системе, получить вэтой же системе число 2n.2.58 A={ | }. Пусть слово P является записью числа 2n (n=0, 1, 2, …) вединичной системе. Получить в этой же системе число n.352.59 Пусть P имеет вид Q+R, где Q и R – непустые слова из символов 0, 1 и 2.Трактуя Q и R как записи троичных чисел (возможно, с незначащими нулями),выдать в качестве ответа запись суммы этих чисел в той же троичной системе.2.60 Пусть P имеет вид Q–R, где Q и R – непустые слова из символов 0, 1 и 2.Трактуя Q и R как записи неотрицательных троичных чисел (возможно, снезначащими нулями) и считая, что Q≥R, выдать в качестве ответа записьразности этих чисел в той же троичной системе.2.61 Пусть P имеет вид Q=R, где Q и R – любые слова из символов a и b.Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе.2.62 Пусть P имеет вид Q=R, где Q и R – непустые слова из символов 0 и 1.Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями),выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.2.63 Пусть P имеет вид Q>R, где Q и R – непустые слова из символов 0 и 1.Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями),выдать в качестве ответа слово 1, если число Q больше числа R, и слово 1 иначе.2.64 A={( , )}.

Определить, сбалансировано ли слово P по круглым скобкам.Ответ: Д (да) или Н (нет)2.65 A={a,b}. Перевернуть слово P (например: abb → bba).3. Задачи теоретического характераВ разделе рассматриваются несложные задачи по теории алгоритмов. Приэтом приводятся необходимые сведения из этой теории. В качестве алгоритмовв основном используются нормальные алгоритмы Маркова (НАМ).В разделе применяются следующие обозначения:1. Последовательность из n подряд идущих символов a будем обозначать как an;например: a0 – это пустое слово, a1 – это a, a4 – это aaaa и т.д.2.

Фраза «слово в алфавите A» означает, что в слово входят лишь символы из А.3. Если алгоритм H применим к слову Р, тогда результат применения H к Р(выходное слово) будем обозначать как H(Р).3.1 Применимость алгоритмаНапомним, что алгоритм называется применимым к слову, если, начавработать над этим словом как входным, он остановится через конечное числошагов. Если же алгоритм зацикливается, то он неприменим к этому слову.Отметим, что когда просят определить, применим алгоритм к слову илинет, то требуется лишь указать, остановится ли алгоритм, и не требуетсяуказывать, каков результат применения алгоритма к слову.36Область применимости алгоритма относительно некоторого алфавита –это множество всех таких слов в этом алфавите, к которым применим алгоритм.Пример 1Определить область применимости следующего НАМ относительно алфавита {a,b}:(1)⎧ b→b⎨ aab( 2)⎩(Напомним, что номера не входят в формулы, а используются лишь для ссылокна них.)РешениеФормула (1) применима к любому входному слову, в которое входит хотябы один символ b, причём она не меняет это слово.

Поэтому на таких словахданный НАМ зацикливается. Если же во входном слове нет символов b, но естьхотя бы один символ a, тогда формула (1) не будет работать, а сработаетзаключительная формула (2), которая остановит алгоритм. Следовательно, НАМостанавливается на словах, состоящих только из символов a. Что же касаетсяпустого входного слова, то в этом случае обе формулы неприменимы, поэтомуНАМ сразу остановится.Итак, область применимости указанного НАМ – все слова вида an (n≥0).Пример 2Построить НАМ, который применим ко всем словам в алфавите {a,b,c}, кромедвух слов – abc и baac.РешениеИз условия задачи следует, что НАМ должен зацикливаться на двухуказанных словах. Однако это не значит, что задачу решает следующий НАМ:⎧ abc → abc⎨ baac → baac⎩Дело в том, что данный алгоритм зацикливается не только на этих двух словах,но и на любых словах, в которые они входят как подслова, например, на словеccabcbb.Поэтому надо как-то отличать случай, когда каждое из указанных словцеликом составляет входное слово, от случая всех остальных слов.

Обычно в такойситуации поступают следующим образом: начало и конец входного слова Pпомечают какими-то спецзнаками (например, *P#), а затем используют формулы, влевой части которых указывают нужные слова и эти спецзнаки (*abc# и *baac#).Такие формулы будут применимы только к нужным входным словам.В нашем примере эти формулы должны зацикливать алгоритм, а дляостанова его на других словах можно использовать, например, формулу * a .Итого, получаем:37⎧ # a → a#⎪ # b → b#⎪ # c → c#⎪⎨ * abc # → * abc #⎪ * baac # → * baac #⎪*a⎪→ *#⎩3.2 Самоприменимость алгоритмаВ первом приближении самоприменимым называют алгоритм (скажем,НАМ), который примени́м к самому себе.

Однако это некорректное определение, поскольку на вход НАМ можно подавать только слова (линейные последовательности символов), а НАМ таковым не является. Поэтому, чтобы сделатьэто определение корректным, надо как-то «вытянуть» НАМ в линию. Для этоговводится понятие записи алгоритма: записью НАМ называется слово, состоящее из последовательно записанных через точку с запятой формул подстановки этого алгоритма (точки с запятой отделяют друг от друга соседние формулы). При этом предполагается, что точки с запятой не входят в формулы; еслиэто не так, то вместо точки с запятой можно использовать любой другой символ, не входящий в формулы.Пусть, к примеру, имеются следующие алгоритмы H1 и H2:⎧ # a → # (1)⎪⎧ a → b (4)Н2: ⎨Н1: ⎨ # a(2)⎩ b → bb (5)⎪⎩→ # (3)Тогда записью алгоритма H1 является слово#a→#;# a ;→#а записью алгоритма H2 – словоa→b;b→bbЛегко понять, что алгоритм однозначно определяет свою запись инаоборот.

Учитывая это, а также то, что запись алгоритма является словом,которое уже можно подавать на вход алгоритму, в указанном выше определениинужно заменить фразу «примени́м к самому себе» на фразу «примени́м к своейзаписи». В результате получаем следующее корректное определение самоприменимости: алгоритм называется самоприменимым, если он примени́м к своейзаписи, и несамоприменимым в противном случае.Например, алгоритм H1 самоприменим, т.к.