Как удалить символ в машине тьюринга

Навигация

Календарь

Машина Тьюринга. Задачи и решения

Один из важнейших вопросов современной информатики — существует ли формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя. ответ на этот вопрос был получен почти одновременно двумя выдающимися учеными — А. Тьюрингом и Э. Постом. Предложенные ими исполнители отличались друг от друга, но оказалось, что они могут имитировать друг друга, а главное — имитировать работу любого формального исполнителя.

Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.

Рассмотрим работу Машины Тьюринга.

Машина Тьюринга представляет собой бесконечную ленту, поделенную на ячейки, и каретку (считывающе-печатающее устройство), которая движется вдоль ленты.

Таким образом Машина Тьюринга формально описывается набором двух алфавитов:

A= — внешний алфавит, служит для записи исходных данных

Q= — внутренний алфавит, описывает набор состояний считывающе-печатного устройства.

Каждая ячейка ленты может содержать символ из внешнего алфавита A = (В нашем случае A=<0, 1>)

Допустимые действия Машины Тьюринга таковы:

1) записать какой-либо символ внешнего алфавита в ячейку ленты (символ, бывший там до того, затирается)

2) сместиться в соседнюю ячейку

3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q

Машина Тьюринга — это автомат, который управляется таблицей.

Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q = . В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 — это конечное состояние, попав в него, автомат заканчивает работу.

В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «

Источник

Решение задач. Машина Тьюринга

Написать программу на машине Тьюринга, прибавляющую число 2 к введенному числу.

Написать на машине Тьюринга программу, прибавляющую 3 к введенному числу.

Перенести первый символ непустого слова P в его конец. Алфавит : A=.

Если первый символ – это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c.

Для решения этой задачи предлагается выполнить следующие действия:

В противном случае уничтожить всё входное слово ( q ₇ ).

Запомнить первый символ, стереть второй символ и установить на его месте первый.

Сдвиг символов осуществляется так: в очередной клетке записываем b (если в q ₁ ) или c (если в q ₂ ), переходим вправо и меняем состояние на q ₁ (если в текущей клетке было записано b ) или на q ₂ (если было записано c ), где осуществляется дальнейшая запись. Если в очередной клетке записано a или пробел, то записываем в нее запомненный символ и останавливаем программу.

После этого возвращаемся к началу входного слова.

Вначале записываем знак = за входным словом. Затем возвращаемся под первый символ входного слова.

Источник

Машина Тьюринга. Удаление подслова.Как его правильно провести?

По заданию необходимо удалить из текста подслова вида ‘abc’.
Понимаю, что сначала нужно прочитать текст, чтоб найти данные подслова. Затем, обнаружив их пометить-обозначить, например как 123, и только после этого удалять.

Машина Тьюринга. Нужно правильно вычислить функцию f(x;y)=x+2y
В машине тьюринга вычислить функцию. Алгоритм выполнения есть, необходимо скинуть файл с ее.

Машина Тьюринга. Нужно правильно вычислить функцию f(x;y)=2x+y
Нужно правильно вычислить функцию f(x;y)=2x+y. Благодарю заранее)

Какую функцию f (x,y) правильно вычисляет машина Тьюринга с программой
ТЕСТ:(можно с решением) Какую функцию f (x,y) правильно вычисляет машина Тьюринга с программой

Машина Тьюринга. Приписать слева к непустому слову P его первый символ
Помочь найти в интернете решение задачи. А=. Приписать слева к непустому слову P его первый.

Даже помечать цифрами ничего не надо. После того, как нашли подстроку abc, поставить в текущую позицию пробел (то есть стереть «c»), а потом сделать два шага назад, на каждом шагу заменяя букву на пробел. Потом вернуться назад к первой букве после стёртого «abc» и продолжить поиск.

Машина Тьюринга: Удалить из слова Р его второй символ, если такой есть
Машина Тьюринга 1. А=. Удалить из слова Р его второй символ, если такой есть. 2. A=.

Источник

Разработка машин Тьюринга

Пример №1 – Замена символа и перемещение головки.

Пусть Р не пустое слово поступающее на вход МТ. Необходимо получить число на 1 больше чем входное.

1. Переместить головку к последней цифре числа;

2. Если эта цифра от 0 до 8, нужно заменить цифрой больше на 1 и остановиться;

3. Ели цифра 9 то заменить на 0 и переместиться к предыдущему разряду, т.е. сдвинуть ленту вправо. Повторяем действия 2 и 3.

4. Если считана пустая ячейка то число состояло из одних 9 и заменяем S₀ на 1 и стоп.

q₄ – добавляем что бы стирать незначащие нули.

Пример №2 – Анализ символов.

Дан алфавит , первый символ не пустого слова Р переместить в конец.

1. Запоминаем первый символ и стираем его;

2. Перемещаемся в конец, на пустую ячейку;

3. Пишем запомненный символ.

Для запоминания символа используются состояния автомата, в данном случае: q1 = a, q2 = b, q3 = c.

Пример №3 – Сравнение символов и стирание слова.

Дан алфавит , если первый и последний символы не пустого слова Р одинаковы, то слова не менять, иначе – стереть.

1. Запоминаем первый символ слова, не стирая его, перемещаемся в конец слова;

2. Если первый и последний символы совпадают то стоп;

3. Если не одинаковы заменяем S₀ и двигаемся вправо. Повторяем это действие пока не дойдем до S₀.

Пример №4 – Удаление символов.

Дан алфавит , из входного слова Р удалить второй символ.

1. Запомнить первый символ, стереть его и переместить ленту влево;

2. Записать запомненный символ во вторую ячейку, стоп.

Пример №5 – Сжатие слова.

Дан алфавит , из входного слова Р удалить первое вхождение символа а.

1. Анализируем первый символ, если это а→S₀ и стоп. Если это b или c запоминаем его и стираем, переходим в соответствующее состояние;

2. Анализируем следующий символ если, а то вместо него пишем b или c и стоп. Если другой запоминаем и пишем предыдущий запомненный символ.

Пример №6 – Вставка символа в слово.

Дан алфавит , если входное слово Р не пустое, то после его первого символа вставить символ а.

1. Анализируем первый символ и запоминаем его, записываем вместо него а, возвращаемся на одну позицию назад.

2. В пустую ячейку записываем запомненный символ и стоп.

Пример №7 – Раздвижка слова.

Входной алфавит в слово Р вставить а после первого вхождения символа с.

1. Перемещаем ленту влево пока не встретим символ с;

2. Вместо с записываем а, перемещаемся вправо;

3. Запоминаем символ ячейки, записываем с, сдвигаемся вправо. Повторяем пока не дойдем до S₀, вместо которого пишем запомненный символ и стоп.

Пример №8 – Формирование слова на новом месте.

Дан алфавит , удалить из входного слова Р все символы а.

Данную задачу можно решать, зациклив алгоритм удаления заданного символа, но задача будет решаться проще, если формировать новое слово без символа а.

1. Перемещаемся в конец слова и добавляем туда символ =;

2. Возвращаемся к началу слова;

3. Запоминаем первый символ и удаляем его, если это был символ а, то переходим к следующему символу. Если это другой символ, то перемещаемся в конец слова, где записываем запомненный символ;

Действия 2 и 3 повторяем до тех пор пока первым символом слова не окажется знак =, удаляем его и останавливаем МТ.

Пример №9 – Фиксирование места на ленте.

Входной алфавит удвоить входное слово Р, поставить между ним и его копией =.

Для фиксирования позиции в которую необходимо вернуться используется метод замены считаного символа его дубликатом: а→А, b→B.

1. В конец слова записываем =4;

2. Возвращаемся к первому символу входного слова;

3. Если первый символ а заменяем на А и двигаемся в конец слова, где записываем копию а. тоже самое делаем с символом b.

4. Возвращаемся к первому не прочитанному символу, заменяя дубликат на исходный символ.

Действия 3 и 4 повторяем до тех пор пока не скопированы все символы.

Машина Тьюринга с двумя выходами

Определить имеется ли во входном слове подслово System

Многоленточная машина Тьюринга

Устройство управления машины в каждый момент времени находится в одном из состояний множества q. Конфигурация машины считается заданной, если известно начальное состояние, входные слова каждой из лент и указана какая из ячеек каждой ленты считывается в данный момент àконфигурация машины задается последовательно, где n-количество лент

И при этом менять или нет содержимое считанной ячейки

Разработать МТ, которая позволяет сложить 2 числа в троичной системе исчисления

Результат поверх первого оператора

Композиции машин Тьюринга

С математической точки зрения машина Тьюринга — просто определенный алгоритм для переработки слов.

Операции композиции, выполняемые над алгоритмами, позволяют образовы-вать новые, более сложные алгоритмы из ранее известных простых алгоритмов. Поскольку машина Тьюринга—алгоритм, то операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них, а именно: произведение, возве-дение в степень, итерацию.

Операция итерации применима к одной машине и определяется следующим образом. Пусть машина Т₁ имеет несколько заключительных состояний. Выберем ее r-е заключительное состояние и отождествим его в схеме машины с ее начальным состоянием. Полученная машина является результатом итерации машины Т₁: T = Т₁. Итерация. Это операция применима, когда в Q существует несколько заключит. состояний. Выбирается одно или несколько из них и отождествляется с начальным состоянием этого же алгоритма

Применима только к одной машине

Если исходная машина Т1 имеет одно заключительное состояние, то результат ее итерации – это машина без заключительного состояния.

Если итерация производится над машиной, которая является результатом умножения и итерации других машин, то соответственно количество точек ставится над теми машинами, чьи заключительные и начальные состояния отождествлялись.

Дана МТ с таблицей состояний

-стирает все 1 слева

-Поиск первой группы единиц после группы 0 справа от начальной ячейки и останавливается после последней 1 в этой группе

-Начинает работу с заполненной ячейки. Движется влево до тех пор пока не встречает группу 1 и останавливается после этой группы через 2 ячейки

Нормальные алгоритмы Маркова (НАМ)

Алгоритмическая система, основанная на соответствии м/у словами в абстрактном алфавите включает в себя объекты двух видов

-элементарные операторы (ЭО)

-элементарные распознаватели 0(ЭР)

ЭО- просто задаваемые алфавитные операторы с помощью последовательного выполнения которых реализуется конкретные алгоритмы

ЭР- распознавание тех или иных свойств перерабатываемой алгоритмом информации и изменения ее в зависимости от результата распознавания с помощью следующих за ними ЭО

Для составления порядка ЭО и ЭР удобно пользоваться ориентированным графом который называется граф-схемой алгоритма

Вершина с одним входом- входная

Вершина с одним выходом- выход

ЭР-2входа и 2выхода

Если входное слово P, поданое на вход граф-схемы, проходя через ее вершины преобразуется и попадает на выход через конечное число шагов, то считается, что этот алгоритм применим к слову P, т.е слово P входит в область определения алгоритма.

Результатом воздействия на входное слово P будет слово на выходе граф-схемы.

В нормальных алгоритмах в качестве элементарного оператора используется оператор подстановки, а в качестве ЭР – распознаватель вхождения( входит ли подслово Р в слово А)

Оператор подстановки заменяет найденное подслово Р на некоторое заданное слово S.

bc->cb- оператор подстановки

Последовательность слов, получаемых в процессе выполнения алгоритма называется дедуктивной ценочной, ведущей от входного слова к выходному.

Алгоритмы, составленные только из распозн. вхожд. и операторов подстановок называются обобщенными нормальными алгоритмами

Нормальными алгоритмами называются такие обобщенные нормальные алгоритмы граф-схемы которых удовлетворяют условиям:

1. Все узлы-распознаватели упорядочиваются и нумеруются от 1 до n.

2. Дуги, исходящие из операторов подстановок присоединяются либо к первому распознавателю либо к выходной вершине

Входная вершина подсоединяется к первому распознавателю

Если ЭО соединяется с выходом он называется заключительным

Наличие в нормальных алгоритмах двух подстановок являются необходимыми условиями универсальности нормального алгоритма т.е возле построения нормального алгоритма эквивалентного любому наперед заданному алгоритму.

Универсальность формируется из принципа нормализации для любого алгоритма в произведении конечном алгоритму А можно построить эквивалентный ему нормальный алгоритм алфавита А.

Понятие “над алфавитом А” в отличии от “ в алфавите А” означает, что в нормальном алгоритме используются символы, отсутствовавшие в А, но этот алгоритм обработка слова в алфавите А и результатом есть слова в алфавите А.

Одноместная частичная, словарная функция F(p) заданная в алфавите А называется нормально вычислимой, если существует нормальный алгоритм N над алфавитом А такой, что

для каждого слова р в алфавите А выполнено равенство F(p) —N(p).

Ā= <0,1,2>расширяем исходный алфавит А

Основные выводы по Нормальным алгоритмам Маркова:

1. В нормальных алгоритмах Маркова используется элементарное действие – подстановка. Формирующие подстановки являются записью выражения £->ϐ, где £ и ϐ- любые слова. При этом £- левая часть формулы, ϐ- правая.

2. Суть подстановки сводится к тому, что во входном слове отыскивается часть, совпадающая с £ и заменяется ϐ, остальные части слова не меняются.

3. Если £ входит в P, то говорят, что формула применима и к P

4. Если £ не входит в P, то подстановка не выполняется и формула не выполняема к P.

5. Если £ входит несколько раз, то на правую часть (P) заменяется только первое входное £

6. Если ϐ- пустое слово, то из P удаляется £

7. Если £- пустое слово, то слева к слову P значения ϐ

НАМ- называется непустой конечный упорядоченный набор формул подстановок

Разработать Нормальный алгоритм Маркова означает определить набор формул.

Правила выполнения НАМ:

1. На каждом шаге входящие в НАМ формулы просматривается и выбирается первая из формул применимая к З. Выполняется подстановка и выполняется новое слово P`

Если на очередном шаге не применима ни одна из формул НАМ тоже прекращаем работу

Вставка и удаление символа

С учетом сказанного нашу задачу должен, казалось бы решать такой НАМ:

Однако это не так. Проверим этот НАМ на входном слове abbcabbca

Напомним, что на каждом шаге работы НАМ формулы подстановки всегда просматриваются сверху вниз начиная с первой из них. Поэтому, пока применима первая формула, она и будет применяться, блокируя доступ к остальным формулам. Это означает, что в НАМ важен порядок перечисления формул подстановки.

Учтем это и переставим наши две формулы

Проверим этот новый алгоритм на том же входном слове:

Вот теперь наш алгоритм будет работать правильно:

Слово, которое получилось после применения заключительной формулы, является выходным словом, т.е результатом применения НАМ к заданному входному слову.

Проверим наш НАМ еще и на входном слове, в которое не входит bb:

К последнему слову (dab) неприменима ни одна формула, поэтому, согласно определению НАМ алгоритм останавливается и это слово объявляется выходным.

Казалось бы для решения этой задачи нужен сложный НАМ. Однако это не так, задача решается с помощью НАМ, содержащего всего одну формулу:

Пока в слове P справа хотя бы от одного символа “b” есть символ “a”, эта формула будет переносить “a” налево от этого “b”. Формула перестает работать, когда справа от “b” нет ни одного “a”, это означает, что все “a” оказались слева от b. Например:

Алгоритм остановился на последнем слове, т.к к нему уже неприменима наша формула.

Этот и предыдущий примеры показывают, что в НАМ, в отличие от машины Тьюринга, легко реализуются подстановки, вставки, и удаления символов. Однако в НАМ возникает другая проблема: как зафиксировать символ(подслово), который должен быть обработан? Рассмотрим эту проблему на следующем примере.

Пример 3 (использование спецзнака) А=<а,b>. Удалить из непустого слова Р его первый символ. Пустое слово не менять.

Ясно, что удалив первый символ слова, надо тут же остановиться. Поэтому, казалось бы, задачу решает следущий НАМ:

Однако это неправильный алгоритм, в чём можно убедиться, применив его к слову bbaba:

Как видно, этот НАМ удалил не первый символ слова, а первое вхождение символа “a”, а это разные вещи. Данный алгоритм будет правильно работать, только если входное слово начинается с символа “а”. Ясно, что перестановка формул в этом НАМ не поможет, т.к. тогда он будет, напротив, неправильно работать на словах, начинающихся с “а”.

Что делать? Надо как-то зафиксировать, пометить первый символ слова, например, поставив перед ним какой-либо знак, скажем *

Итого, получаем следущий НАМ:

Проверим его на том же входном слове:

Проверим данный алгоритм:

Казалось бы, всё в порядке. Однако это не так: наш алгоритм зациклится на пустом входном слове, т.к. постоянно будет применяться формула (3), а согласно условию задачи на таком слове НАМ должен остановиться. В чём при­чина этой ошибки? Дело в том, что мы ввели знак * для того, чтобы пометить первый символ слова, а затем уничтожить * и этот символ. Но в пустом слове нет ни одного символа, поэтому формулы (1) и (2) ни разу не сработают и по­стоянно будет выполняться формула (3). Следовательно, чтобы учесть случай пустого входного слова, надо после формул (1) и (2) записать ещё одну фор­мулу, которая уничтожает «одинокую» звёздочку и останавливает алгоритм:

Вот теперь мы наконец-то составили правильный алгоритм.

Прежде чем перейти к следующим задачам, обобщим тот приём со звёздочкой, который мы использовали в примере 3.

Пусть в обрабатываемое слово Р входит несколько раз подслово а:

Этот приём со спецзнаком следует запомнить, т.к. в НАМ он используется очень часто.

Правда, остаётся еще одна проблема: как спецзнак разместить рядом с нужным вхождением “а”? Следующие примеры показывают, как это делается.

Пример 4 (фиксация спецзнаком заменяемого символа)

Но этот алгоритм неправильный, в чём можно убедиться на входном слове 0123:

Ошибка здесь в том, что после замены четверичной цифры на пару двоичных цифр уже никак нельзя отличить двоичные цифры от четверичных, поэтому наш НАМ начинает заменять и двоичные цифры. Значит, надо как-то отделить ту часть числа, в которой уже была произведена замена, от той части, где замены ещё не было. Для этого предлагается пометить слева спецзнаком * ту четверичную цифру, которая сейчас должна быть заменена на пару соот­ветствующих двоичных цифр, а после того как такая замена будет выполнена, спецзнак нужно поместить перед следующей четверичной цифрой:

Итого, получаем следующий алгоритм перевода чисел из четверичной системы в двоичную

Проверим этот НАМ на входном слове 0123:

Пример 5 (перемещение спецзнака)

Но как поместить спецзнак в конец слова? Делается это так: сначала спецзнак * приписываем слева к слову Р, а затем «перегоняем» звёздочку через все буквы слова:

С учётом всего сказанного получаем следующий НАМ:

Отметим, что при пустом входном слове этот НАМ сначала введёт звё­здочку, а затем тут же заменит её на символ “а” и остановится.

Пример 6 (смена спецзнака)

А=<а,b>. В слове Р заменить на аа последнее вхождение символа “а”, если такое есть. Например: bababb —> babaabb

Удвоение символа “а” реализуется формулой a |-> аа. Но чтобы она применя­лась не к первому вхождению символа а, а к последнему, надо поставить, ска­жем, справа от последнего символа “а” спецзнак * и применить формулу а* |-> аа.

Реализуем эту идею в виде следующего НАМ:

Здесь формула (6) приписывает * слева к входному слову Р, формулы (1) и (2) перегоняют * в конец Р, после чего формула (3) перемещает * справа налево через все b в конце слова до ближайшего, т.е. последнего, символа “а”, и, наконец, формула (4) заменяет этот символ на аа и останавливает алгоритм. Формула же (5) нужна для входных слов, в которые не входит “а”.

Проверим этот алгоритм на входном слове bababb (двойная стрелка означает несколько шагов применения формул (1) и (2)):

Как видно, вместо того, чтобы двигаться справа влево до ближайшего символа “а”, звёздочка начала «прыгать» вокруг последнего символа слова. Почему? Дело в том, что формулы (1) и (2), перегоняющие * вправо, мешают формуле (3), перегоняющей * влево. Отметим, что перестановка этих формул не поможет, т.к. тогда * начнёт «плясать» вокруг первого символа входного слова. Что делать?

Проверим этот алгоритм на прежнем входном слове:

Если же во входное слово не входит символ а, тогда имеем:

Пример 7 (перенос символа через слово) A=. Перенести в конец непустого слова Р его первый символ. Пустое слово не менять.

Например: bbaba —> babab

Для решения этой задачи предлагается выполнить следующие действия.

1. Помечаем первый символ слова Р спецзнаком *.

2. Заменяем * и этот символ на новый символ: а на А, b на В. Этим мы фактически вводим два новых спецзнака A и B, которые нужны, чтобы отличить первый символ слова от остальных символов при его переносе в конец слова.

4. Наконец, заменяем А или В в конце слова на прежний символ (А на а, В на b) и останавливаем алгоритм.

Все эти действия реализуются в виде следующего НАМ

Здесь формулы (1) и (2) заменяют первый символ слова (вместе с *) на А или B. Формулы (3)-(6) перегоняют А и В в конец слова. Формулы (7) и (8) применяются только тогда, когда А и В окажутся в конце слова (когда за ними уже нет символов), и восстанавливают исходный вид первого символа. Формула (9) нужна на случай пустого входного слова. Формула же (10) ставит спецзнак * перед первым символом.

Проверим этот алгоритм на входном слове bаbа и на входном слове из одного символа:

первым символом слова и остальными символами не будет, т.к. только перед первым символом находится звёздочка.

Итак, возможен и следущий НАМ, решающий нашу задачу:

Проверим этот алгоритм на прежнем входном слове bbaba:

Пример 8 (использование нескольких спецзнаков)

Предлагается следующий план решения задачи:

1. Приписываем к концу слова Р символ =, справа от которого будем строить копию Р.

2. Просматриваем по очереди все символы слова Р и, не уничтожая их, переносим копию каждого символа в конец.

3. Удаляем символ =, который отделял слово Р от его копии, и останавливаем алгоритм.

Теперь уточним этот план.

Как приписать некоторый символ к концу слова, мы уже знаем: надо сначала приписать слева к слову какой-то спецзнак, скажем *, затем перегнать его направо через все символы слова и в конце, когда за * не окажется никакого символа, заменить на символ =:

Из предыдущего примера мы также знаем, как переносить символы слова в конец слова. Только теперь сами символы уничтожать уже не надо. Поэтому поступаем так: если надо скопировать символ а, то порождаем за ним новый символ А (заменяем а на аА),после чего этот символ А переставляем с каждым последующим символом (в том числе и с символом =), перенося тем самым А в конец слова, где и заменяем на а:

Когда справа от спецзнака # окажется символ =, это будет означать, что входное слово полностью скопировано. Осталось только уничтожить символы # и = после чего остановиться.

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

С учетом всего сказанного получаем следующий НАМ:

Здесь формулы (1)-(3) «перегоняют» звёздочку в конец входного слова и заменяют её на символ =. Формулы (4)-(7) перегоняют символ А в конец слова, после чего заменяют на a. Формулы (8)—(11) делают то же самое с В и b. Формулы (12 и (13) «вводят в игру» символы А и В, соответствующие тому символу входного слова, который должен быть скопирован следующим.

Формула (14) применяется только тогда, когда справа от # нет ни а, ни b, т.е. когда полностью просмотрено всё входное слово. И, наконец, формула (15) вводит сразу два спецзнака # и *.

15 1,2 3 12 4-6 8 12

12 8-10 11 12 8-10 11

Приведём ещё одно решение задачи удвоения слова, в котором предлагается выполнить следующие действия.

3. Как видно, справа мы получили копию входного слова, но записанную большими буквами. Осталось только заменить их на малые буквы. Вот здесь-то и понадобится спецзнак #: будем перемещать его влево через каждую большую букву с заменой её на малую. Когда слева от # уже не окажется большой буквы,
надо уничтожить # и остановиться:

Все указанные действия описываются в виде следующего НАМ

2.3 Задачи для самостоятельного решения

1) В задачах рассматриваются только целые неотрицательные числа, если не сказано иное.

2.1 A=,h,p>. В слове Р заменить все пары ph на f

,h_,p). В слове Р заменить на f только первую пару ph, если такая есть.

2.3 А=<а_,b,с]. Приписать слово bас слева к слову Р.

2.4 А=<а_,b,с]. Заменить слово Р на пустое слово, т.е. удалить из Р все символы.

2.5 А=<а_,b,с>. Заменить любое входное слово на слово а.

2.6 Выписать НАМ, не меняющий входное слово (при любом алфавите А).

1.Создается копия каждого символа входного слова в виде альтернативного символа

Спец.символ * помечает тот символ входного слова, который еще не имеет копии. Когда созданы все копии * меняется на #

2.Копии символов перегоняются в конец исходного слова и размещаются перед #

3.Символы-копии заменяются на исходные символы. При этом # помечает ту копию, которая еще не преобразована.

Задачи теоретического характера

Последовательность из n-подряд идущих одинаковых символов. Слово в алфавите А означает, что слово состоит только из символов входного алфавита.

Если некоторый алгоритм H применим к слову P, то результат-H(P)

Алгоритм считается применимым к входному слову P если при обр. этого слова он остановится через конечное слово шагов.

Областью применимости алгоритма относительно некоторого алфавита называется множество таких слов в алфавите к которым алгоритм применим.

Определить область применимости НАМ относительно алфавита А=

Областью применимости алгоритма являются слова, состоящие только из символов a

Областью применимости являются все слова, содержащие хотя бы 1 символ “a” или пустое слово

Построить НАМ который применим ко всем словам, кроме abc

Самоприменимость- применимость алгоритмов к самим себе. Это не совсем корректно т.к на вход НАМ должны подаваться линейные последовательности символов, а НАМ таковой не является.

Для применения данного алфавита к НАМ его алгоритм необходимо вывести в линию.

Запись НАМ- словоЮ состоящее из последовательно записанных формул подстановки через ;

Тогда самоприменимость НАМ- применимость алгоритма к его записи.

Несамоприменимый алгоритм, т.к он заканичивается

Построить НАМ, который не самоприменим, но применим к любому слову b

Для решения этой задачи необходимо чтобы в алгоритме команда, выполняющая замену символов, отсутствующих во входном алфавите. Тогда такой алгоритм зацикливатся на своей записи, но обраб. символы извходного алфавита

Проблема самоприменимости алгоритмически неразрешима, т.е не существует единого алгоритма, позволяющего определить саморименим ли алгоритм. Однако в частных случаях эта задача разрешима, а именно, если алгоритм состоит из одной подстановки.

Если алгоритм состоит из одной подстановки, то по его виду можно определить самоприменим ли он

Метод проверки самоприменимости

Если ед.форма алгоритма заключительная, то такой алгоритм всегда самоприменим. Если ед.форма алгоритма обычная, то такой алгоритм будет самоприменим, если левая часть подстановки не входит правую часть подстановки

Эквивалентными называются алгоритмы которые предлагают разные способы решения для одной и той же задачи, т.е для одинаковых входных слов эти алгоритмы выдают одинаковые выходные слова.

Необходимо учитывать, для оценки эквивалентности зацикливания алгоритма т.е если какой-то алгоритм зацикливается на некотором наборе слов, то эквив. след. также должен зацикливатся на таком же наборе слов.

Определить эквивалентны ли следующие пары НАМ относительно A=

Источник