Пильщиков абрамов машина тьюринга и алгоритмы маркова

Машина Тьюринга и алгоритмы Маркова. Решение задач

1 Московский государственный университет им. М.В. Ломоносова Факультет вычислительной математики и кибернетики В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая Машина Тьюринга и алгоритмы Маркова. Решение задач (Учебно-методическое пособие) Москва, 2006

4 Такт работы машины Тьюринга МТ работает тактами, которые выполняются один за другим. На каждом такте автомат МТ выполняет три следующих действия, причем обязательно в указанном порядке: 1) записывает некоторый символ S в видимую клетку (в частности, может быть записан тот же символ, что и был в ней, тогда содержимое этой клетки не меняется); 2) сдвигается на одну клетку влево (обозначение L, от left), либо на одну клетку вправо (обозначение R, от right), либо остается неподвижным (обозначение N). 3) переходит в некоторое состояние q (в частности, может остаться в прежнем состоянии). Формально действия одного такта будем записывать в виде тройки: S, [L,R,N], q где конструкция с квадратными скобками означает возможность записи в этом месте любой из букв L, R или N. Например, такт *,L,q8 означает запись символа * в видимую клетку, сдвиг на одну клетку влево и переход в состояние q8. Программа для машины Тьюринга Сама по себе МТ ничего не делает. Для того чтобы заставить её работать, надо написать для неё программу. Эта программа записывается в виде следующей таблицы: q 1 q j q m S 1 S 2 S i S n Λ S, [L, R, N], q Слева перечисляются все состояния, в которых может находиться автомат, сверху все символы (в том числе и Λ), которые автомат может видеть на ленте. (Какие именно символы и состояния указывать в таблице определяет автор программы.) На пересечениях же (в ячейках таблицы) указываются те такты, которые должен выполнить автомат, когда он находится в соответствующем состоянии и видит на ленте соответствующий символ. В целом таблица определяет действия МТ при всех возможных конфигурациях и тем самым полностью задаёт поведение МТ. Описать алгоритм в виде МТ значит предъявить такую таблицу. (Замечание. Часто МТ определяют как состоящую из ленты, автомата и программы, поэтому при разных программах получаются разные МТ. Мы же будет считать, в духе современных компьютеров, что МТ одна, но она может выполнять разные программы.) 4

6 2) Второй исход «плохой»: это когда МТ зацикливается, никогда не попадая на такт останова (например, автомат на каждом шаге сдвигается вправо и потому не может остановиться, т.к. лента бесконечна). В этом случае говорят, что МТ неприменима к заданному входному слову. Ни о каком результате при таком исходе не может идти и речи. Отметим, что один и тот же алгоритм (программа МТ) может быть применимым к одним входным словам (т.е. останавливаться) и неприменимым к другим (т.е. зацикливаться). Таким образом, применимость/неприменимость зависит не только от самого алгоритма, но и от входного слова. На каких входных словах алгоритм должен останавливаться? На, так сказать, хороших словах, т.е. на тех, которые относятся к допустимым исходным данным решаемой задачи, для которых задача осмысленна. Но на ленте могут быть записаны любые входные слова, в том числе и те, для которых задача не имеет смысла; на таких словах поведение алгоритма не фиксируется, он может остановиться (при любом результате), а может и зациклиться. Соглашения для сокращения записи Договоримся о некоторых соглашениях, сокращающих запись программы для МТ. 1) Если в такте не меняется видимый символ, или автомат не сдвигается, или не меняется состояние автомата, то в соответствующей позиции такта мы не будем ничего писать. Например, при конфигурации следующие записи тактов эквивалентны: a,r,q3,r,q3 (но не Λ,R,q3!!) b,n,q2 b,,q2 a,l,q1,l, a,n,q1,, (это такт останова) Замечание. Запятые в тактах желательно не опускать, т.к. иначе возможна путаница, если среди символов на ленте могут встретиться буквы L и R. 2) Если надо указать, что после выполнения некоторого такта МТ должна остановиться, то в третьей позиции этого такта будем писать знак «!». Например, такт b,l,! означает следующие действия: запись символа b в видимую клетку ленты, сдвиг влево и останов. Формально можно считать, что в программе МТ имеется состояние с названием!, во всех ячейках которого записаны такты останова. При этом, однако, такую строку явно не выписывают, а лишь подразумевают. 3) Если заранее известно, что в процессе выполнения программы не может появиться некоторая конфигурация, тогда, чтобы подчеркнуть это явно, будем в соответствующей ячейке таблицы рисовать крестик. (Формально этот крестик считается тактом останова.) Эти соглашения необязательны, но они сокращают запись программы и упрощают её восприятие. 6

7 1.2 Примеры на составление программ для МТ Рассмотрим примеры на составление программ для МТ, чтобы продемонстрировать некоторые типичные приёмы программирования на МТ. Для сокращения формулировки задач введём следующие два соглашения: буквой Р будем обозначать входное слово; буквой А будем обозначать алфавит входного слова, т.е. набор тех символов, из которых и только которых может состоять Р (отметим, однако, что в промежуточных и выходном словах могут появляться и другие символы). Пример 1 (перемещение автомата, замена символов) А=<0,1,2,3,4,5,6,7,8,9>. Пусть Р непустое слово; значит, Р это последовательность из десятичных цифр, т.е. запись неотрицательного целого числа в десятичной системе. Требуется получить на ленте запись числа, которое на 1 больше числа Р. Решение. Для решения этой задачи предлагается выполнить следующие действия: 1. Перегнать автомат под последнюю цифру числа. 2. Если это цифра от 0 до 8, то заменить её цифрой на 1 больше и остановиться; например: Если же это цифра 9, тогда заменить её на 0 и сдвинуть автомат к предыдущей цифре, после чего таким же способом увеличить на 1 эту предпоследнюю цифру; например: Особый случай: в Р только девятки (например, 99). Тогда автомат будет сдвигаться влево, заменяя девятки на нули, и в конце концов окажется под пустой клеткой. В эту пустую клетку надо записать 1 и остановиться (ответом будет 100): В виде программы для МТ эти действия описываются следующим образом: Λ q1 0,R,q1 1,R,q1 2,R,q1 3,R,q1 4,R,q1 5,R,q1 6,R,q1 7,R,q1 8,R,q1 9,R,q1 Λ,L,q2 q2 1,N,! 2, N,! 3, N,! 4, N,! 5, N,! 6, N,! 7, N,! 8, N,! 9, N,! 0,L,q2 1,N,! Пояснения. q1 это состояние, в котором автомат «бежит» под последнюю цифру числа. Для этого он всё время движется вправо, не меняя видимые цифры и оставаясь в том же состоянии. Но здесь есть одна особенность: когда автомат находится под 7

8 последней цифрой, то он ещё не знает об этом (ведь он не видит, что записано в соседних клетках) и определит это лишь тогда, когда попадёт на пустую клетку. Поэтому, дойдя до первой пустой клетки, автомат возвращается назад под последнюю цифру и переходит в состояние q2 (вправо двигаться уже не надо). q2 это состояние, в котором автомат прибавляет 1 к той цифре, которую видит в данный момент. Сначала это последняя цифра числа; если она в диапазоне от 0 до 8, то автомат заменяет её цифрой, которая на 1 больше, и останавливается. Но если это цифра 9, то автомат заменяет её на 0 и сдвигается влево, оставаясь в состоянии q2. Тем самым, он будет теперь прибавлять 1 к предыдущей цифре. Если и эта цифра равна 9, то автомат заменяет её на 0 и сдвигается влево, оставаясь попрежнему в состоянии q2, т.к. должен выполнить то же самое действие увеличить на 1 видимую цифру. Если же автомат сдвинулся влево, а в видимой клетке нет цифры (а есть «пусто»), то он записывает сюда 1 и останавливается. Отметим, что для пустого входного слова наша задача не определена, поэтому на этом слове МТ может вести себя как угодно. В нашей программе, например, при пустом входном слове МТ останавливается и выдает ответ 1. Выше мы привели запись программы в полном, несокращённом виде. Теперь же приведём запись программы в сокращённом, более наглядном виде, при этом справа дадим краткое пояснение действий, которые реализуются в соответствующих состояниях автомата: Λ q1,r,,r,,r,,r,,r,,r,,r,,r,,r,,r,,l,q2 под последнюю цифру q2 1. 2. 3. 4. 5. 6. 7. 8. 9. 0,L, 1. видимая цифра + 1 Именно так мы и будем в дальнейшем записывать программы. Пример 2 (анализ символов) А=. Перенести первый символ непустого слова Р в его конец. Например: a b c b b c b a Решение. Для решения этой задачи предлагается выполнить следующие действия: 1. Запомнить первый символ слова P, а затем стереть этот символ. 2. Перегнать автомат вправо под первую пустую клетку за P и записать в неё запомненный символ. Как «бегать» вправо, мы уже знаем из предыдущего примера. А вот как запомнить первый символ? Ведь в МТ нет другого запоминающего устройства, кроме ленты, а запоминать символ в какой-то клетке на ленте бессмысленно: как только автомат сдвинется влево или вправо от этой клетки, он тут же забудет данный символ. Что делать? Выход здесь таков надо использовать разные состояния автомата. Если первый символ это a, то надо перейти в состояние q2, в котором автомат 8

9 бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c. Следовательно, то, каким был первый символ, мы фиксируем переводом автомата в разные состояния. Это типичный приём при программировании на МТ. С учётом сказанного программа будет такой: a b c Λ q1 Λ,R,q2 Λ,R,q3 Λ,R,q4,R, анализ 1-го символа, удаление его, разветвление q2,r,,r,,r, a. запись a справа q3,r,,r,,r, b. запись b справа q4,r,,r,,r, c. запись c справа Рассмотрим поведение этой программы на входных словах, содержащих не более одного символа. При пустом слове, которое является «плохим» для задачи, программа зациклится автомат, находясь в состоянии q1 и попадая всё время на пустые клетки, будет бесконечно перемещаться вправо. (Конечно, в этом случае программу можно было бы остановить, но мы специально сделали зацикливание, чтобы продемонстрировать такую возможность.) Если же во входном слове ровно один символ, тогда автомат сотрёт этот символ, сдвинется на одну клетку вправо и запишет в неё данный символ: c c q1 q4! Таким образом, слово из одного символа попросту сдвинется на клетку вправо. Это допустимо. Ведь клетки ленты не нумерованы, поэтому местоположение слова на ленте никак не фиксируется и перемещение слова влево или вправо заметить нельзя. В связи с этим не требуется, чтобы выходное слово обязательно находилось в том же месте, где было входное слово, результат может оказаться и левее, и правее этого места. Пример 3 (сравнение символов, стирание слова) А=. Если первый и последний символы (непустого) слова Р одинаковы, тогда это слово не менять, а иначе заменить его на пустое слово. Решение. Для решения этой задачи предлагается выполнить следующие действия: 1. Запомнить первый символ входного слова, не стирая его. 2. Переместить автомат под последний символ и сравнить его с запомненным. Если они равны, то больше ничего не делать. 3. В противном случае уничтожить всё входное слово. Как запоминать символ и как перегонять автомат под последний символ слова, мы уже знаем из предыдущих примеров. Стирание же входного слова реализуется 9

10 заменой всех его символов на символ Λ. При этом, раз уж автомат оказался в конце слова, будем перемещать автомат справа налево до первой пустой клетки. Эти действия описываются следующей программой для МТ (напомним, что крестик в ячейке таблицы означает невозможность появления соответствующей конфигурации при выполнении программы): a b c Λ q1,,q2,,q4,,q6. анализ 1-го символа, разветвление q2,r,,r,,r,, L,q3 идти к последнему символу при 1-м символе a q3. q8,, q8 сравнить посл. символ с a, не равны на q8 (стереть P) q4,r,,r,,r,, L,q5 аналогично при 1-м символе b q5,, q8. q8 q6,r,,r,,r,, L,q7 аналогично при 1-м символе c q7,, q8,, q8. q8 Λ,L, Λ,L, Λ,L. стереть всё слово, двигаясь справа налево Пример 4 (удаление символа из слова) А=. Удалить из слова Р его второй символ, если такой есть. Решение. Казалось бы, эту задачу решить просто: надо сдвинуть автомат под клетку со вторым символом и затем очистить эту клетку: a b b a a b b a a b a Однако напомним, что внутри выходного слова не должно быть пустых клеток. Поэтому после удаления второго символа надо «сжать» слово, перенеся первый символ на одну клетку вправо. Для этого автомат должен вернуться к первому символу, запомнить его и стереть, а затем, снова сдвинувшись вправо, записать его в клетку, где был второй символ. Однако начальный «поход» вправо ко второму символу, чтобы его стереть, и последующий возврат к первому символу являются лишними действиями: какая разница переносить первый символ в пустую клетку или в клетку с каким-то символом? Поэтому сразу запоминаем первый символ, стираем его и записываем вместо второго символа: a b b a b b a a b a В виде программы для МТ всё это записывается так: a b Λ q1 Λ,R,q2 Λ,R,q3. анализ и удаление 1-го символа, разветвление q2. a. a. замена 2-го символа на a q3 b. b. замена 2-го символа на b Пример 5 (сжатие слова) А=. Удалить из слова Р первое вхождение символа a, если такое есть. Решение. В предыдущем примере мы переносили на позицию вправо только один сим- 10

12 первый символ (на старом месте его можно пока не удалять), а затем, вернувшись на старое место, записать символ a: b c a b c a b b c a b a c a Перенос символа на одну позицию влево аналогичен переносу символа вправо, о чём говорилось в двух предыдущих примерах, поэтому приведем программу для МТ без дополнительных комментариев. Отметим лишь, что в состояниях q2, q3 и q4 автомат может видеть только пустую клетку, а в состоянии q5 он обязательно видит первый символ входного слова, но не пустую клетку. a b c Λ q1,l,q2,l,q3,l,q4. анализ 1-го символа для переноса его влево q2 a,r,q5 приписать a слева q3 b,r,q5 приписать b слева q4 c,r,q5 приписать c слева q5. a. a. заменить бывший 1-й символ на a Пример 7 (раздвижка слова) А=. Вставить в слово P символ a за первым вхождением символа c, если такое есть. Решение. Просматриваем входное слово слева направо до пустой клетки или до первого символа c. В первом случае c не входит в P, поэтому ничего не делаем. Во втором случае надо освободить место для вставляемого символа a, для чего сдвигаем начало слова P (от первого символа до найденного символа c) на одну позицию влево. При этом осуществляем такой сдвиг справа налево от символа c к началу слова, раз уж автомат находится под этим символом. Кроме того, чтобы затем не возвращаться к освободившейся позиции, начинаем этот сдвиг с записи a вместо найденного символа c. Поскольку этот циклический сдвиг влево реализуется аналогично циклическому сдвигу вправо из примера 5, то не будем пояснять его, а сразу приведём программу для МТ: a b c Λ q1,r,,r, a,l,q4,l,! вправо до с, вставка a вместо c, перенос c влево q2,l, a,l,q3 a,l,q4 a. перенос a справа q3 b,l,q2,l, b,l,q4 b. перенос b справа q4 c,l,q2 c,l,q3,l, c. перенос c справа Пример 8 (формирование слова на новом месте) А=. Удалить из P все вхождения символа a. Решение. Предыдущие примеры показывают, что в МТ достаточно сложно реализуются вставки символов в слова и удаления символов из слов. Поэтому иногда проще не раздвигать или сжимать входное слово, а формировать выходное сло- 12

13 во в другом, свободном месте ленты. Именно так мы и поступим при решении данной задачи. Конкретно предлагается выполнить следующие действия: 1. Выходное слово будем строить справа от входного. Чтобы разграничить эти слова, отделим их некоторым вспомогательным символом, например знаком =, отличным от всех символов алфавита A (см. шаг 1). (Напомним, что на ленте могут быть записаны не только символы из алфавита входного слова.) 2. После этого возвращаемся к началу входного слова (см. шаг 2). a b c a b c = a b c = Теперь наша задача перенести в цикле все символы входного слова, кроме a, вправо за знак = в формируемое выходное слово. Для этого анализируем первый символ входного слова. Если это a, тогда стираем его и переходим к следующему символу (см. шаг 3). Если же первый символ это b или c, тогда стираем его и «бежим» вправо до первой пустой клетки (см. шаг 4), куда и записываем этот символ (см. шаг 5). b c = c = c = b Снова возвращаемся налево к тому символу, который стал первым во входном слове, и повторяем те же самые действия, но уже по отношению к этому символу (см. шаги 6-9). c = b = b = b c Этот цикл завершается, когда при возврате налево мы увидим в качестве первого символа знак =. Это признак того, что мы полностью просмотрели входное слово и перенесли все его символы, отличные от a, в формируемое справа выходное слово. Надо этот знак стереть, сдвинуться вправо под выходное слово и остановиться (см. шаг 10). = b c b c 9 10 С учётом всего сказанного и строим программу для МТ. При этом отметим, что помимо символов a, b и c в процессе решения задачи на ленте появляется знак =, поэтому в таблице должен быть предусмотрен столбец и для этого знака. a b c = Λ q1,r,,r,,r, =,,q2 записать справа знак = q2,l,,l,,l,,l,,r,q3 влево к 1-му символу слова q3 Λ,R, Λ,R,q4 Λ,R,q5 Λ,R,! анализ и удаление его, разветвление q4,r,,r,,r,,r, b,,q2 запись b справа, возврат налево (в цикл) q5,r,,r,,r,,r, c,,q2 запись c справа, возврат налево (в цикл) 13

14 Пример 9 (фиксирование места на ленте) А=. Удвоить слово P, поставив между ним и его копией знак =. Например: a a b a a b = a a b Решение. Эта задача решается аналогично предыдущей: в конец входного слова записываем знак =, затем возвращаемся к началу слова и в цикле все его символы (в том числе и a) копируем в пустые клетки справа: a a b a a b = a a b = a a b = a 1 2 Однако есть и отличие: копируемые символы входного слова не удаляются, и это приводит к следующей проблеме. Записав справа копию очередного символа, мы затем должны вернуться к входному слову в позицию этого символа и потом сдвинуться вправо к следующему символу, чтобы скопировать уже его. Но как узнать, в какую позицию входного слова надо вернуться? Например, откуда мы знаем в нашем примере, что после копирования первого символа a мы должны вернуться именно к первому символу входного слова, а не ко второму или третьему? В предыдущей задаче мы всегда возвращались к первому из оставшихся символов входного слова, а теперь мы сохраняем все символы, поэтому непонятно, какие символы мы уже скопировали, а какие ещё нет. Отметим также, что в МТ ячейки ленты никак не нумеруются, нет в МТ и счетчиков, которые позволили бы определить, сколько символов мы уже скопировали. В общем виде проблема, с которой мы столкнулись, следующая: как зафиксировать на ленте некоторую позицию, в которой мы уже были и к которой позже должны вернуться? Обычно эта проблема решается так. Когда мы оказываемся в этой позиции в первый раз, то заменяем находящийся в ней символ на его двойник на новый вспомогательный символ, причем разные символы заменяем на разные двойники, например a на A и b на B. После этого мы выполняем какие-то действия в других местах ленты. Чтобы затем вернуться к нашей позиции, надо просто отыскать на ленте ту клетку, где находится символ A или B. Затем в данной клетке можно восстановить прежний символ, если нам больше не надо фиксировать эту позицию (именно для восстановления прежнего символа и надо было заменять разные символы на разные двойники). Воспользуемся этим приёмом в нашей задаче, выполняя следующие действия: 1. Как уже сказано, вначале записываем знак = за входным словом (см. шаг 1 выше). 2. Затем возвращаемся под первый символ входного слова (см. шаг 2 выше). 3. Далее заменяем видимый символ a на двойник A (см. шаг 3 ниже), «бежим» вправо до первой свободной клетки и записываем в неё символ a (см. шаг 4). После этого возвращаемся влево к клетке с двойником A (см. шаг 5), восстанавливаем прежний символ a и сдвигаемся вправо к следующему символу (см. шаг 6). 14

16 1.4 A=. Оставить в слове P только первый символ (пустое слово не менять). 1.5 A=. Оставить в слове P только последний символ (пустое слово не менять). 1.6 A=. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе. 1.7 A=. Определить, входит ли в слово P символ a. Ответ: слово из одного символа a (да, входит) или пустое слово (нет). 1.8 A=. Если в слово P не входит символ a, то заменить в P все символы b на с, иначе в качестве ответа выдать слово из одного символа a. 1.9 A=. Определить, является ли слово P идентификатором (непустым словом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет) A=. Определить, является ли слово P записью числа в двоичной системе счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ: слово 1 (да) или слово A=<0,1>. Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть A=<0,1>. Для непустого слова P определить, является ли оно записью степени двойки (1, 2, 4, 8, ) в двоичной системе счисления. Ответ: слово 1 (является) или слово A=<0,1,2,3>. Считая непустое слово P записью числа в четверичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или A=<0,1>. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное учетверенному числу P (например: ) A=<0,1>. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное неполному частному от деления числа P на 2 (например: ) A=. Если P слово чётной длины (0, 2, 4, ), то выдать ответ a, иначе пустое слово A=<0,1,2>. Считая непустое слово P записью числа в троичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0. (Замечание: в чётном троичном числе должно быть чётное количество цифр 1.) 1.18 A=. Пусть P имеет нечётную длину. Оставить в P только средний символ A=. Если слово P имеет чётную длину, то оставить в нём только левую половину A=. Приписать слева к непустому слову P его первый символ. 16

17 1.21 A=. Для непустого слова P определить, входит ли в него ещё раз его первый символ. Ответ: a (да) или пустое слово A=. В непустом слове P поменять местами его первый и последний символы A=. Определить, является P палиндромом (перевёртышем, симметричным словом) или нет. Ответ: a (да) или пустое слово A=. Заменить в P каждое вхождение a на bb A=. Заменить в P каждое вхождение ab на c A=. Удвоить слово P (например: abb abbabb) A=. Удвоить каждый символ слова P (например: bab bbaabb) A=. Перевернуть слово P (например: abb bba) A=<0,1>. Считая непустое слово P записью двоичного числа, получить это же число, но в четверичной системе. (Замечание: учесть, что в двоичном числе может быть нечётное количество цифр.) 1.30 A=<0,1,2,3>. Считая непустое слово P записью числа в четверичной системе счисления, получить запись этого числа в двоичной системе A=<0,1,2>. Считая непустое слово P записью положительного числа в троичной системе счисления, уменьшить это число на A=< >. Считая слово P записью числа в единичной системе счисления, получить запись этого числа в троичной системе. (Рекомендация: следует в цикле удалять из «единичного» числа по палочке и каждый раз прибавлять 1 к троичному числу, которое вначале положить равным 0.) 1.33 A=<0,1,2>. Считая непустое слово P записью числа в троичной системе счисления, получить запись этого числа в единичной системе Пусть слово P имеет следующий вид: <. <. n m где один из знаков +. /,, или, слева от которого указано n палочек, а справа m палочек. Реализовать соответствующую операцию в единичной системе счисления (в качестве ответа выдать слово, указанное справа от стрелки): а) сложение: <. + <. <. (n 0, m 0) n m n+ m б) вычитание: <. <. <. (n m 0) n m n m в) умножение: <. <. <. (n 0, m 0) n m n m г) деление нацело: <<. /. <. (n 0, m>0, k=n div m) n m k д) взятие остатка: <. <. <. (n 0, m>0, k=n mod m) n m k 17

18 е) максимум: <. <. <. (n 0, m 0, k=max(n,m)) n m k ж) минимум: <. <. <. (n 0, m 0, k=min(n,m)) k n m 1.35 A=< >. Считая слово P записью числа в единичной системе, определить, является ли это число степенью 3 (1, 3, 9, 27, ). Ответ: пустое слово, если является, или слово из одной палочки иначе A=< >. Считая слово P записью числа n в единичной системе, получить в этой же системе число 2 n A=< >. Пусть слово P является записью числа 2 n (n=0, 1, 2, ) в единичной системе. Получить в этой же системе число n Пусть P имеет вид Q+R, где Q и R непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи чисел в троичной системе счисления (возможно, с незначащими нулями), выдать в качестве ответа запись суммы этих чисел в той же троичной системе Пусть P имеет вид Q R, где Q и R непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи чисел в троичной системе счисления (возможно, с незначащими нулями) и считая, что Q R, выдать в качестве ответа запись разности этих чисел в той же троичной системе Пусть P имеет вид Q=R, где Q и R любые слова из символов a и b. Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе Пусть P имеет вид Q=R, где Q и R непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе Пусть P имеет вид Q>R, где Q и R непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе A=<(, )>. Определить, сбалансировано ли слово P по круглым скобкам. Ответ: Д (да) или Н (нет) A=. Если в P символов a больше, чем символов b, то выдать ответ a, если символов a меньше символов b, то выдать ответ b, а иначе в качестве ответа выдать пустое слово. 2. Нормальные алгоритмы Маркова В разделе рассматриваются задачи на составление нормальных алгоритмов Маркова. Приводится краткое описание этих алгоритмов, на примерах объясняются основные приёмы их составления и предлагаются задачи для самостоятельного решения. 18

19 2.1 Краткое описание нормальных алгоритмов Маркова Подстановки Интересной особенностью нормальных алгоритмов Маркова (НАМ) является то, что в них используется лишь одно элементарное действие так называемая подстановка, которая определяется следующим образом. Формулой подстановки называется запись вида α β (читается «α заменить на β»), где α и β любые слова (возможно, и пустые). При этом α называется левой частью формулы, а β правой частью. Сама подстановка (как действие) задается формулой подстановки и применяется к некоторому слову Р. Суть операции сводится к тому, что в слове Р отыскивается часть, совпадающая с левой частью этой формулы (т.е. с α), и она заменяется на правую часть формулы (т.е. на β). При этом остальные части слова Р (слева и справа от α) не меняются. Получившееся слово R называют результатом подстановки. Условно это можно изобразить так: P x α y R x β y Необходимые уточнения: 1. Если левая часть формулы подстановки входит в слово Р, то говорят, что эта формула применима к Р. Но если α не входит в Р, то формула считается неприменимой к Р, и подстановка не выполняется. 2. Если левая часть α входит в Р несколько раз, то на правую часть β, по определению, заменяется только первое вхождение α в Р: P x α y α z R x β y α z 3. Если правая часть формулы подстановки пустое слово, то подстановка α сводится к вычеркиванию части α из Р (отметим попутно, что в формулах подстановки не принято как-либо обозначать пустое слово): P x α y R x y 4. Если в левой части формулы подстановки указано пустое слово, то подстановка β сводится, по определению, к приписыванию β слева к слову P: P x R β x Из этого правила вытекает очень важный факт: формула с пустой левой частью применима к любому слову. Отметим также, что формула с пустыми левой и правой частями не меняет слово. Определение НАМ Нормальным алгоритмом Маркова (НАМ) называется непустой конечный упорядоченный набор формул подстановки: 19

20 α1 β1 α 2 β 2. ( k 1) α k β k В этих формулах могут использоваться два вида стрелок: обычная стрелка ( ) и стрелка «с хвостиком» ( a ). Формула с обычной стрелкой называется обычной формулой, а формула со стрелкой «с хвостиком» заключительной формулой. Разница между ними объясняется чуть ниже. Записать алгоритм в виде НАМ значит предъявить такой набор формул. Правила выполнения НАМ Прежде всего, задается некоторое входное слово Р. Где именно оно записано не важно, в НАМ этот вопрос не оговаривается. Работа НАМ сводится к выполнению последовательности шагов. На каждом шаге входящие в НАМ формулы подстановки просматриваются сверху вниз и выбирается первая из формул, применимых к входному слову Р, т.е. самая верхняя из тех, левая часть которых входит в Р. Далее выполняется подстановка согласно найденной формуле. Получается новое слово Р. На следующем шаге это слово Р берется за исходное и к нему применяется та же самая процедура, т.е. формулы снова просматриваются сверху вниз начиная с самой верхней и ищется первая формула, применимая к слову Р, после чего выполняется соответствующая подстановка и получается новое слово Р. И так далее: Р Р Р Следует обратить особое внимание на тот факт, что на каждом шаге формулы в НАМ всегда просматриваются начиная с самой первой. Необходимые уточнения: 1. Если на очередном шаге была применена обычная формула (α β), то работа НАМ продолжается. 2. Если же на очередном шаге была применена заключительная формула (α a β), то после её применения работа НАМ прекращается. То слово, которое получилось в этот момент, и есть выходное слово, т.е. результат применения НАМ к входному слову. Как видно, разница между обычной и заключительной формулами подстановки проявляется лишь в том, что после применения обычной формулы работа НАМ продолжается, а после заключительной формулы прекращается. 3. Если на очередном шаге к текущему слову неприменима ни одна формула, то и в этом случае работа НАМ прекращается, а выходным словом считается текущее слово. Таким образом, НАМ останавливается по двум причинам: либо была применена заключительная формула, либо ни одна из формул не подошла. То и другое считается «хорошим» окончанием работы НАМ. В обоих случаях говорят, что НАМ применúм к входному слову. 20

Источник