В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая - Машина Тьюринга и алгоритмы Маркова. Решение задач (1000390), страница 4
Текст из файла (страница 4)
Ответ: 1 (да) или 0.(Замечание: в чётном троичном числе должно быть чётное количество цифр 1.)1.18 A={a,b,c}. Пусть P имеет нечётную длину. Оставить в P только среднийсимвол.1.19 A={a,b,c}. Если слово P имеет чётную длину, то оставить в нём тольколевую половину.1.20 A={a,b,c}. Приписать слева к непустому слову P его первый символ.161.21 A={a,b}.
Для непустого слова P определить, входит ли в него ещё раз егопервый символ. Ответ: a (да) или пустое слово.1.22 A={a,b}. В непустом слове P поменять местами его первый и последнийсимволы.1.23 A={a,b}. Определить, является P палиндромом (перевёртышем, симметричным словом) или нет. Ответ: a (да) или пустое слово.1.24 A={a,b}. Заменить в P каждое вхождение a на bb.1.25 A={a,b,c}. Заменить в P каждое вхождение ab на c.1.26 A={a,b}.
Удвоить слово P (например: abb → abbabb).1.27 A={a,b}. Удвоить каждый символ слова P (например: bab → bbaabb).1.28 A={a,b}. Перевернуть слово P (например: abb → bba).1.29 A={0,1}. Считая непустое слово P записью двоичного числа, получить этоже число, но в четверичной системе. (Замечание: учесть, что в двоичном числеможет быть нечётное количество цифр.)1.30 A={0,1,2,3}. Считая непустое слово P записью числа в четверичнойсистеме счисления, получить запись этого числа в двоичной системе.1.31 A={0,1,2}.
Считая непустое слово P записью положительного числа втроичной системе счисления, уменьшить это число на 1.1.32 A={ | }. Считая слово P записью числа в единичной системе счисления,получить запись этого числа в троичной системе. (Рекомендация: следует вцикле удалять из «единичного» числа по палочке и каждый раз прибавлять 1 ктроичному числу, которое вначале положить равным 0.)1.33 A={0,1,2}. Считая непустое слово P записью числа в троичной системесчисления, получить запись этого числа в единичной системе.1.34 Пусть слово 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)nmk17| ... | ↑ |{| ... | → |{| ... | (n≥0, m≥0, k=max(n,m))е) максимум: |{nmkж) минимум: |{| ... | ↓ |{| ...
| → |{| ... | (n≥0, m≥0, k=min(n,m))nmk1.35 A={ | }. Считая слово P записью числа в единичной системе, определить,является ли это число степенью 3 (1, 3, 9, 27, …). Ответ: пустое слово, еслиявляется, или слово из одной палочки иначе.1.36 A={ | }. Считая слово P записью числа n в единичной системе, получить вэтой же системе число 2n.1.37 A={ | }.
Пусть слово P является записью числа 2n (n=0, 1, 2, …) в единичной системе. Получить в этой же системе число n.1.38 Пусть P имеет вид Q+R, где Q и R – непустые слова из символов 0, 1 и 2.Трактуя Q и R как записи чисел в троичной системе счисления (возможно, снезначащими нулями), выдать в качестве ответа запись суммы этих чисел в тойже троичной системе.1.39 Пусть P имеет вид Q–R, где Q и R – непустые слова из символов 0, 1 и 2.Трактуя Q и R как записи чисел в троичной системе счисления (возможно, снезначащими нулями) и считая, что Q≥R, выдать в качестве ответа записьразности этих чисел в той же троичной системе.1.40 Пусть P имеет вид Q=R, где Q и R – любые слова из символов a и b.Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе.1.41 Пусть P имеет вид Q=R, где Q и R – непустые слова из символов 0 и 1.Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями),выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.1.42 Пусть P имеет вид Q>R, где Q и R – непустые слова из символов 0 и 1.Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями),выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе.1.43 A={(, )}.
Определить, сбалансировано ли слово P по круглым скобкам.Ответ: Д (да) или Н (нет).1.44 A={a,b}. Если в P символов a больше, чем символов b, то выдать ответ a,если символов a меньше символов b, то выдать ответ b, а иначе в качествеответа выдать пустое слово.2. Нормальные алгоритмы МарковаВ разделе рассматриваются задачи на составление нормальных алгоритмовМаркова. Приводится краткое описание этих алгоритмов, на примерахобъясняются основные приёмы их составления и предлагаются задачи длясамостоятельного решения.182.1 Краткое описание нормальных алгоритмов МарковаПодстановкиИнтересной особенностью нормальных алгоритмов Маркова (НАМ)является то, что в них используется лишь одно элементарное действие – такназываемая подстановка, которая определяется следующим образом.Формулой подстановки называется запись вида α→β (читается «αзаменить на β»), где α и β – любые слова (возможно, и пустые). При этом αназывается левой частью формулы, а β – правой частью.Сама подстановка (как действие) задается формулой подстановки иприменяется к некоторому слову Р.
Суть операции сводится к тому, что в словеР отыскивается часть, совпадающая с левой частью этой формулы (т.е. с α), иона заменяется на правую часть формулы (т.е. на β). При этом остальные частислова Р (слева и справа от α) не меняются. Получившееся слово R называютрезультатом подстановки. Условно это можно изобразить так:Pαx→yRβxyНеобходимые уточнения:1.
Если левая часть формулы подстановки входит в слово Р, то говорят, чтоэта формула применима к Р. Но если α не входит в Р, то формула считаетсянеприменимой к Р, и подстановка не выполняется.2. Если левая часть α входит в Р несколько раз, то на правую часть β, поопределению, заменяется только первое вхождение α в Р:Pxααy→zRβxyαz3. Если правая часть формулы подстановки – пустое слово, то подстановкаα→ сводится к вычеркиванию части α из Р (отметим попутно, что в формулахподстановки не принято как-либо обозначать пустое слово):Pαx→yRxy4.
Если в левой части формулы подстановки указано пустое слово, топодстановка →β сводится, по определению, к приписыванию β слева к слову P:Px→RβxИз этого правила вытекает очень важный факт: формула с пустой левойчастью применима к любому слову. Отметим также, что формула с пустымилевой и правой частями не меняет слово.Определение НАМНормальным алгоритмом Маркова (НАМ) называется непустой конечныйупорядоченный набор формул подстановки:19⎧ α1 → β1⎪ α2 → β2⎨ ...(k ≥ 1)⎪αβ→k⎩ kВ этих формулах могут использоваться два вида стрелок: обычная стрелка (→)и стрелка «с хвостиком» ( a ).
Формула с обычной стрелкой называетсяобычной формулой, а формула со стрелкой «с хвостиком» – заключительнойформулой. Разница между ними объясняется чуть ниже.Записать алгоритм в виде НАМ – значит предъявить такой набор формул.Правила выполнения НАМПрежде всего, задается некоторое входное слово Р. Где именно онозаписано – не важно, в НАМ этот вопрос не оговаривается.Работа НАМ сводится к выполнению последовательности шагов. Накаждом шаге входящие в НАМ формулы подстановки просматриваются сверхувниз и выбирается первая из формул, применимых к входному слову Р, т.е.самая верхняя из тех, левая часть которых входит в Р. Далее выполняетсяподстановка согласно найденной формуле. Получается новое слово Р′.На следующем шаге это слово Р′ берется за исходное и к нему применяется та же самая процедура, т.е.
формулы снова просматриваются сверху внизначиная с самой верхней и ищется первая формула, применимая к слову Р′,после чего выполняется соответствующая подстановка и получается новоеслово Р′′. И так далее:Р → Р′ → Р′′ → …Следует обратить особое внимание на тот факт, что на каждом шагеформулы в НАМ всегда просматриваются начиная с самой первой.Необходимые уточнения:1. Если на очередном шаге была применена обычная формула (α→β), торабота НАМ продолжается.2. Если же на очередном шаге была применена заключительная формула(α a β), то после её применения работа НАМ прекращается. То слово, котороеполучилось в этот момент, и есть выходное слово, т.е. результат примененияНАМ к входному слову.Как видно, разница между обычной и заключительной формуламиподстановки проявляется лишь в том, что после применения обычной формулыработа НАМ продолжается, а после заключительной формулы – прекращается.3.
Если на очередном шаге к текущему слову неприменима ни одна формула, то и вэтом случае работа НАМ прекращается, а выходным словом считается текущее слово.Таким образом, НАМ останавливается по двум причинам: либо былаприменена заключительная формула, либо ни одна из формул не подошла. То идругое считается «хорошим» окончанием работы НАМ. В обоих случаяхговорят, что НАМ применúм к входному слову.20Однако может случиться и так, что НАМ никогда не остановится; этопроисходит, когда на каждом шаге есть применимая формула и эта формулаобычная.
Тогда говорят, что НАМ неприменим к входному слову. В этомслучае ни о каком результате нет и речи.2.2 Примеры на составление НАМРассмотрим примеры, в которых демонстрируются типичные приёмысоставления НАМ.Как и в случае машины Тьюринга, для сокращения формулировки задачбудем использовать следующие соглашения:– буквой Р будем обозначать входное слово;– буквой А будем обозначать алфавит входного слова, т.е. набор тех символов,которые и только которые могут входить во входное слово Р (но в процессевыполнения НАМ в обрабатываемых словах могут появляться и другие символы).Кроме того, в примерах будем справа от формул подстановки указыватьих номера.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
