Пример №1 – Замена символа и перемещение головки.
А = {0,1,2,3,4,5,6,7,8,9}
Пусть Р не пустое слово поступающее на вход МТ. Необходимо получить число на 1 больше чем входное.
Действия:
1. Переместить головку к последней цифре числа;
2. Если эта цифра от 0 до 8, нужно заменить цифрой больше на 1 и остановиться;
3. Ели цифра 9 то заменить на 0 и переместиться к предыдущему разряду, т.е. сдвинуть ленту вправо. Повторяем действия 2 и 3.
4. Если считана пустая ячейка то число состояло из одних 9 и заменяем S0 на 1 и стоп.
S0 | |||||||||||
q0 | q0Л | q0Л | q0Л | q0Л | q0Л | q0Л | q0Л | q0Л | q0Л | q0Л | q1п |
q1 | q3 1С | q3 2С | q3 3С | q3 4С | q3 5С | q3 6С | q3 7С | q3 8С | q3 9С | q2 0П | - |
q2 | q3 1С | q3 2С | q3 3С | q3 4С | q3 5С | q3 6С | q3 7С | q3 8С | q3 9С | q2 0П | q3 1С |
q4 | q4 S0Л | q0Л | q0Л | q0Л | q0Л | q0Л | q0Л | q0Л | q0Л | q0Л | q3 1С |
q4 – добавляем что бы стирать незначащие нули.
q02345
q0 2→ q0Л 2q0345
q03→ q0Л 23q045
q04→ q0Л 234q05
q05→ q0Л 2345q0
q0S0→ q1П 234q15
q15→ q36С 234q36
Пример №2 – Анализ символов.
Дан алфавит {a,b,c}, первый символ не пустого слова Р переместить в конец.
|
|
Действия:
1. Запоминаем первый символ и стираем его;
2. Перемещаемся в конец, на пустую ячейку;
3. Пишем запомненный символ.
Для запоминания символа используются состояния автомата, в данном случае: q1 = a, q2 = b, q3 = c.
a | b | c | S0 | |
q0 | q1 S0Л | q2 S0Л | q3 S0Л | q4C |
q1 | q1Л | q1Л | q1Л | q4aC |
q2 | q2Л | q2Л | q2Л | q4bC |
q3 | q3Л | q3Л | q3Л | q4cC |
q0baca
q0b→ q2 S0Л q2aca
q2a→ q2Л aq2ca
q2c→ q2Л acq2a
q2a→ q2Л acaq2
q2 S0→q4bC acaq4b
Пример №3 – Сравнение символов и стирание слова.
Дан алфавит {a,b,c}, если первый и последний символы не пустого слова Р одинаковы, то слова не менять, иначе – стереть.
Действия:
1. Запоминаем первый символ слова, не стирая его, перемещаемся в конец слова;
2. Если первый и последний символы совпадают то стоп;
3. Если не одинаковы заменяем S0 и двигаемся вправо. Повторяем это действие пока не дойдем до S0.
a | b | c | S0 | |
q0 | q1Л | q2Л | q3Л | q8C |
q1 | q1Л | q1Л | q1Л | q4П |
q2 | q2Л | q2Л | q2Л | q5П |
q3 | q3Л | q3Л | q3Л | q6П |
q4 | q8C | q7 S0П | q7 S0П | - |
q5 | q7 S0П | q8 S0C | q7 S0П | - |
q6 | q7 S0П | q7 S0П | q8 S0C | - |
q7 | q7 S0П | q7 S0П | q7 S0П | q8C |
q0babc
q0b→ q2Л bq2abc
q2a→ q2Л baq2bc
q2b→ q2Л babq2c
q2c→ q2Л babcq2
q2S0→ q5П babq5c
q5c→ q7 S0П baq7b
q7b→ q7 S0П bq7a
q7a→ q7 S0П q7b
q7b→ q7 S0П q7S0
q7S0→ q8C q8S0
Пример №4 – Удаление символов.
Дан алфавит {a,b}, из входного слова Р удалить второй символ.
Действия:
1. Запомнить первый символ, стереть его и переместить ленту влево;
2. Записать запомненный символ во вторую ячейку, стоп.
a | b | S0 | |
q0 | q1 S0Л | q2 S0Л | q3C |
q1 | q3aC | q3aC | q3aC |
q2 | q3bC | q3bC | q3bC |
q0bab
q0b→ q2 S0Л q2ab
q2 a→ q3bC q3bb
Пример №5 – Сжатие слова.
Дан алфавит {a,b,с}, из входного слова Р удалить первое вхождение символа а.
Действия:
|
|
1. Анализируем первый символ, если это а→S0 и стоп. Если это b или c запоминаем его и стираем, переходим в соответствующее состояние;
2. Анализируем следующий символ если, а то вместо него пишем b или c и стоп. Если другой запоминаем и пишем предыдущий запомненный символ.
a | b | c | S0 | |
q0 | q3 S0C | q1 S0Л | q2 S0Л | q3C |
q1 | q3bC | q1bЛ | q2bЛ | q3bC |
q2 | q3cC | q1сЛ | q3сЛ | q3cC |
q0baac
q0b→ q1 S0Л q1aac
q1 a→ q3bC q3bac
Пример №6 – Вставка символа в слово.
Дан алфавит {a,b,с}, если входное слово Р не пустое, то после его первого символа вставить символ а.
Действия:
1. Анализируем первый символ и запоминаем его, записываем вместо него а, возвращаемся на одну позицию назад.
2. В пустую ячейку записываем запомненный символ и стоп.
a | b | c | S0 | |
q0 | q1 аП | q2 аП | q3 аП | q4C |
q1 | - | - | - | q4aC |
q2 | - | - | - | q4bC |
q3 | - | - | - | q4cC |
q0bbac
q0b→ q2 aП q2S0abac
q2 S0→ q4bC q4babac
Пример №7 – Раздвижка слова.
Входной алфавит {a,b,c} в слово Р вставить а после первого вхождения символа с.
Действия:
1. Перемещаем ленту влево пока не встретим символ с;
2. Вместо с записываем а, перемещаемся вправо;
3. Запоминаем символ ячейки, записываем с, сдвигаемся вправо. Повторяем пока не дойдем до S0, вместо которого пишем запомненный символ и стоп.
a | b | c | S0 | |
q0 | q0Л | q0Л | q1 аП | q4C |
q1 | q2 cП | q3 cП | - | q4cC |
q2 | q2П | q3 аП | - | q4aC |
q3 | q2 bП | q3П | - | q4bC |
q0abac
q0a→ q0Л aq0bac
q0b→ q0Л abq0ac
q0a→ q0Л abaq0c
q0c→ q1аП abq1aa
q1a→ q2cП aq2bca
q2b→ q3аП q3aaca
q3a→ q2bП q2S0baca
q2S0→ q4aC q4abaca
Пример №8 – Формирование слова на новом месте.
Дан алфавит {a,b,c}, удалить из входного слова Р все символы а.
Данную задачу можно решать, зациклив алгоритм удаления заданного символа, но задача будет решаться проще, если формировать новое слово без символа а.
Действия:
1. Перемещаемся в конец слова и добавляем туда символ =;
2. Возвращаемся к началу слова;
3. Запоминаем первый символ и удаляем его, если это был символ а, то переходим к следующему символу. Если это другой символ, то перемещаемся в конец слова, где записываем запомненный символ;
Действия 2 и 3 повторяем до тех пор пока первым символом слова не окажется знак =, удаляем его и останавливаем МТ.
a | b | c | S0 | = | |
q0 | q0Л | q0Л | q0Л | q1=П | - |
q1 | q1П | q1П | q1П | q2Л | q1П |
q2 | q2S0Л | q3S0Л | q4S0Л | - | q5S0C |
q3 | q3Л | q3Л | q3Л | q1bП | q3Л |
q4 | q4Л | q4Л | q4Л | q1cП | q4Л |
q0cba
q0c→ q0Л c q0ba
q0b→ q0Л cb q0a
q0a→ q0Л cba q0
q0S0→ q1=П cb q1a=
q1a→ q1П c q1ba=
q1b→ q1П q1cba=
q1c→ q1П q1S0cba=
q1S0→ q2Л q2cba=
q2c→ q4S0Л q4ba=
q4b→ q4Л b q4a=
q4a→ q4Л ba q4=
q4=→ q4Л ba= q4
q4S0→ q1cП ba q1=c
q1=→ q1П b q1a=c
q1a→ q1П q1ba=c
q1b→ q1П q1S0ba=c
q1S0→ q2Л q2ba=c
q2b→ q3S0Л q3a=c
q3a→ q3Л a q3=c
q3=→ q3Л a= q3c
q3c→ q3Л a=c q3
q3S0→ q1bП a= q1cb
q1c→ q1П a q1=cb
q1=→ q1П q1a=cb
q1a→ q1П q1S0a=cb
q1S0→ q2Л q2a=cb
q2a→ q2S0Л q2=cb
q2=→ q5S0C q5S0cb
Пример №9 – Фиксирование места на ленте.
Входной алфавит {a,b} удвоить входное слово Р, поставить между ним и его копией =.
Для фиксирования позиции в которую необходимо вернуться используется метод замены считаного символа его дубликатом: а→А, b→B.
Действия:
1. В конец слова записываем =4;
2. Возвращаемся к первому символу входного слова;
3. Если первый символ а заменяем на А и двигаемся в конец слова, где записываем копию а. тоже самое делаем с символом b.
4. Возвращаемся к первому не прочитанному символу, заменяя дубликат на исходный символ.
Действия 3 и 4 повторяем до тех пор пока не скопированы все символы.
a | b | А | В | S0 | = | |
q0 | q0Л | q0Л | - | - | q1=П | - |
q1 | q1П | q1П | q2aЛ | q2bЛ | q2Л | q1П |
q2 | q3AЛ | q4BЛ | - | - | - | q5C |
q3 | q3Л | q3Л | - | - | q1aП | q3Л |
q4 | q4Л | q4Л | - | - | q1bП | q4Л |
q0ba
q0b→ q0Л bq0a
q0a→ q0Л baq0
q0S0→ q1=П bq1a=
q1a→ q1П q1ba=
q1b→ q1П q1S0ba=
q1 S0→ q2Л q2ba=
q2b→ q4BЛ Bq4a=
q4a→ q4Л Baq4=
q4=→ q4Л Ba=q4
q4S0→ q1bП Baq1=b
q1=→ q1П Bq1a=b
q1a→ q1П q1Ba=b
q1B→ q2 bЛ bq2a=b
q2a→ q3AЛ bAq3=b
q3=→ q3Л bA=q3b
q3b→ q3Л bA=bq3
q3S0→ q1аП bA=q1ba
q1b→ q1П bAq1=ba
q1=→ q1П bq1A=ba
q1A→q2aЛ baq2=ba
|
|
q2=→q5C baq5=ba
Машина Тьюринга с двумя выходами
Рассмотрим устройство МТ добавив в устройство управления машиной некоторое состояние При этом -конечное, тогда МТ переходит в если оно принимает слово х и запрещает -MT с двумя выходами
Определить имеется ли во входном слове подслово System
System
S | Y | T | E | M | др | ||
Л | Л | Л | Л | С | Л | ||
Л | Л | Л | Л | C | Л | ||
Л | |||||||
Л | Л | ||||||
Л | |||||||
С |
Многоленточная машина Тьюринга
Схема машины:
▼
Устройство управления машины в каждый момент времени находится в одном из состояний множества q. Конфигурация машины считается заданной, если известно начальное состояние, входные слова каждой из лент и указана какая из ячеек каждой ленты считывается в данный момент àконфигурация машины задается последовательно, где n-количество лент
... …
... …
…
... …
Несмотря на количество лент такая машина может выполнять стандартный набор действий: -лево
-право
-стоять на месте
И при этом менять или нет содержимое считанной ячейки
Пример:
Разработать МТ, которая позволяет сложить 2 числа в троичной системе исчисления
(на 1ленте)ßx=x+yà(2лента)
Результат поверх первого оператора
Σ | ||||||||||||||||
Q | ||||||||||||||||
0Л0Л | 0Л1Л | 0Л2Л | ЛЛ | ЛЛ | ЛЛ | ЛЛ | ПП | ЛЛ | ЛЛ | ЛСЛ | ЛСЛ | ПСЛ | ЛПС | ЛЛС | ЛПС | |
ПП | 1ПП | 2ПП | 1ПП | ПП | 0ПП | 2ПП | СС | 0ПП | 1ПП | 0ПП | 1ПП | 2ПП | СС | СС | СС | |
1ПП | 2ПП | 0ПП | 2ПП | 0ПП | 1ПП | 0ПП | 1СС | 1ПП | 2ПП | 1ПП | 2ПП | ОПП | 1ПП | 2ПП | 0ПП |
Композиции машин Тьюринга
С математической точки зрения машина Тьюринга — просто определенный алгоритм для переработки слов.
Операции композиции, выполняемые над алгоритмами, позволяют образовы-вать новые, более сложные алгоритмы из ранее известных простых алгоритмов. Поскольку машина Тьюринга—алгоритм, то операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них, а именно: произведение, возве-дение в степень, итерацию.
|
|
Пусть заданы машины Тьюринга Т1 и Т2, имеющие какой-то общий внешний алфавит А = {а0, а1,..., аm} и внутренние алфавиты Q1 = {q0, q1,..., qn} и cоответственно Q2 = {q0,q1,…,qt}. Композитом, или произведением, машины Т1 на машину T2 будем называть машину Т с тем же внешним алфавитом А= {а0, а1,..., аm}, внутренним алфавитом Q = {q0, q1,...,qn, qn+1,...,qn+t} и программой, получающейся следующим образом. Во всех командах Т1 содержащих заключитель-ный символ q0, заменяем его на символ qn+1. Все остальные символы в командах T1 оставляем неизменными. В командах Т2, напротив, символ q0 оставляем неизменным, но зато каждый из остальных символов заменяем символом qn+j. Совокупность всех команд Т1 и Т2, измененных указанным способом, и будет программой композита или произведения машин T1 и T2. Произведение машины T1 на машину Т2 обозначается через Т = T1 • T2, или Т = T1 * Т2.
Таким же образом определяется операция возведения в степень: n -й степенью машины T называется произведение T... Т с n сомножителями. Возведение в степень. Это такая МТ, которая повторяет свой раб цикл n раз, при этом заключит. состояние этой МТ "склеивается" со своим же начальным состоянием.
Операция итерации применима к одной машине и определяется следующим образом. Пусть машина Т1 имеет несколько заключительных состояний. Выберем ее r -е заключительное состояние и отождествим его в схеме машины с ее начальным состоянием. Полученная машина является результатом итерации машины Т1: T = Т1. Итерация. Это операция применима, когда в Q существует несколько заключит. состояний. Выбирается одно или несколько из них и отождествляется с начальным состоянием этого же алгоритма
Итерация
Применима только к одной машине
Суть операции:
Пусть некоторая машина Т1 имеет несколько заключительных состояний. Выберем некоторое частное заключительное состояние и отождествим его с начальным состоянием данной машины. Такая машина обозначается.r- заключительное состояние по которому выполнена итерация.
Если исходная машина Т1 имеет одно заключительное состояние, то результат ее итерации – это машина без заключительного состояния.
Если итерация производится над машиной, которая является результатом умножения и итерации других машин, то соответственно количество точек ставится над теми машинами, чьи заключительные и начальные состояния отождествлялись.
Пример:
Дана МТ с таблицей состояний
-стирает все 1 слева
0П |
-Поиск первой группы единиц после группы 0 справа от начальной ячейки и останавливается после последней 1 в этой группе
0Л | 1Л | |
0Л | 1Л | |
0Л | 1Л |
-Начинает работу с заполненной ячейки. Движется влево до тех пор пока не встречает группу 1 и останавливается после этой группы через 2 ячейки
0П | 1П |
-конечные
0С | 1С |
Распознавание символа
-“0”
-“1”
0П | П | |
0С | С | |
0Л | 1Л | |
0С | 0П | |
0С | 1Л | |
0Л | 1Л |
Нормальные алгоритмы Маркова (НАМ)
Алгоритмическая система, основанная на соответствии м/у словами в абстрактном алфавите включает в себя объекты двух видов
-элементарные операторы (ЭО)
-элементарные распознаватели 0(ЭР)
ЭО- просто задаваемые алфавитные операторы с помощью последовательного выполнения которых реализуется конкретные алгоритмы
ЭР- распознавание тех или иных свойств перерабатываемой алгоритмом информации и изменения ее в зависимости от результата распознавания с помощью следующих за ними ЭО
Для составления порядка ЭО и ЭР удобно пользоваться ориентированным графом который называется граф-схемой алгоритма
Вершина с одним входом- входная
Вершина с одним выходом- выход
ЭР-2входа и 2выхода
ЭО- 1вход 1 выход
Если входное слово P, поданое на вход граф-схемы, проходя через ее вершины преобразуется и попадает на выход через конечное число шагов, то считается, что этот алгоритм применим к слову P, т.е слово P входит в область определения алгоритма.
Результатом воздействия на входное слово P будет слово на выходе граф-схемы.
В нормальных алгоритмах в качестве элементарного оператора используется оператор подстановки, а в качестве ЭР – распознаватель вхождения(входит ли подслово Р в слово А)
Оператор подстановки заменяет найденное подслово Р на некоторое заданное слово S.
p->s
bc->cb- оператор подстановки
abcbabca->acbabca->acbacba
Последовательность слов, получаемых в процессе выполнения алгоритма называется дедуктивной ценочной, ведущей от входного слова к выходному.
Алгоритмы, составленные только из распозн. вхожд. и операторов подстановок называются обобщенными нормальными алгоритмами
ba->ab
bc->ba
bb->ac
bc ba ab -> bc ab ab -> bc aabb -> ba aabb -> ab aabb -> aa ba bb -> aaa bb b -> aaaacb
Нормальными алгоритмами называются такие обобщенные нормальные алгоритмы граф-схемы которых удовлетворяют условиям:
1. Все узлы-распознаватели упорядочиваются и нумеруются от 1 до n.
2. Дуги, исходящие из операторов подстановок присоединяются либо к первому распознавателю либо к выходной вершине
Входная вершина подсоединяется к первому распознавателю
Если ЭО соединяется с выходом он называется заключительным
Пример:
A= {+, 1}
1) ‘1+’->’11’
2)’1’->’1’
P=’11+11+1’->’111 1+1’ -> 1 1111->11111
Наличие в нормальных алгоритмах двух подстановок являются необходимыми условиями универсальности нормального алгоритма т.е возле построения нормального алгоритма эквивалентного любому наперед заданному алгоритму.
Универсальность формируется из принципа нормализации для любого алгоритма в произведении конечном алгоритму А можно построить эквивалентный ему нормальный алгоритм алфавита А.
Понятие “над алфавитом А” в отличии от “ в алфавите А” означает, что в нормальном алгоритме используются символы, отсутствовавшие в А, но этот алгоритм обработка слова в алфавите А и результатом есть слова в алфавите А.
Одноместная частичная, словарная функция F(p) заданная в алфавите А называется нормально вычислимой, если существует нормальный алгоритм N над алфавитом А такой, что
для каждого слова р в алфавите А выполнено равенство F(p) —N(p).
Пример:
F(p)=pa F(p)=N(p)
A={0,1}
Ā={0,1,2} расширяем исходный алфавит А
1. 20->02 ->удаление символа слева
2. 2` -> `2;
3. 2-> Q
4. ->2 -дописываем символ слева
F(0110)=0110a
_0110-> 20 110->0 211 0->0 12 10->01102->0110a
Основные выводы по Нормальным алгоритмам Маркова:
1. В нормальных алгоритмах Маркова используется элементарное действие – подстановка. Формирующие подстановки являются записью выражения £->ϐ, где £ и ϐ- любые слова. При этом £- левая часть формулы, ϐ- правая.
2. Суть подстановки сводится к тому, что во входном слове отыскивается часть, совпадающая с £ и заменяется ϐ, остальные части слова не меняются.
3. Если £ входит в P, то говорят, что формула применима и к P
4. Если £ не входит в P, то подстановка не выполняется и формула не выполняема к P.
5. Если £ входит несколько раз, то на правую часть (P) заменяется только первое входное £
6. Если ϐ- пустое слово, то из P удаляется £
7. Если £- пустое слово, то слева к слову P значения ϐ
НАМ- называется непустой конечный упорядоченный набор формул подстановок
При этом используется 2 вида стрелок ->(Обычная подстановочная)
->| (Заключительная подстановка)
|-> (Заключительная подстановка)
->.(Заключительная подстановка)
Разработать Нормальный алгоритм Маркова означает определить набор формул.
Правила выполнения НАМ:
1. На каждом шаге входящие в НАМ формулы просматривается и выбирается первая из формул применимая к З. Выполняется подстановка и выполняется новое слово P`
2. На следующем шаге в качестве входного берется слово P` и к нему применяется (1). Получаем P`` и т.д
В НАМ после получения промежуточного слова формулы просматриваются сначала. Если была применена заключительная формула на очередном этапе, то работа НАМ прекращается.
Если на очередном шаге не применима ни одна из формул НАМ тоже прекращаем работу
Примеры:
Пример 1
Вставка и удаление символа
Дан алфавит А{a,b,c,d} необходимо разработать алгоритм, который заменяет первое вхождение “bb” на “ddd”,а также удалить все символы “c”.
Например: abbcabbca -> adddabba
Решение.
Прежде всего отметим, что в НАМ, в отличие от машины Тьюринга, легко реализуются вставки и удаления символов. Вставка новых символов в слово- это замена некоторого подслова на подслово с большим числом символов; например, с помощью формулы bb -> ddd два символа будут заменены на три символа. При этом не надо заботиться о том, чтобы предварительно освободить место для дополнительных символов, в НАМ слово раздвигается автоматически. Удаление же символов- это замена некоторого подслова на подслово с меньшим числом символов; например, удаление символа “c” реализуется формулой “c->” (с пустой правой частью). При этом никаких пустых позиций внутри слова не появляется, сжатие слова в НАМ происходит автоматически.
С учетом сказанного нашу задачу должен, казалось бы решать такой НАМ:
Однако это не так. Проверим этот НАМ на входном слове abbcabbca
a bb cabbca -> adddca bb ca -> addd c adddca -> adddaddd c a -> …
Как видно, заменив первое вхождение bb на ddd, этот НАМ не перешел сразу к удалению символов “c”, а стал заменять и другие вхождения bb. Почему?
Напомним, что на каждом шаге работы НАМ формулы подстановки всегда просматриваются сверху вниз начиная с первой из них. Поэтому, пока применима первая формула, она и будет применяться, блокируя доступ к остальным формулам. Это означает, что в НАМ важен порядок перечисления формул подстановки.
Учтем это и переставим наши две формулы
Проверим этот новый алгоритм на том же входном слове:
abb c abbca -> abbabb c a -> a bb abba -> addda bb a -> adddaddda
Итак, НАМ сначала удалил все символы “c” и только затем заменил первое вхождение bb на ddd. Однако НАМ на этом не остановился и стал заменять остальные вхождения bb. Почему? Дело в том, что, пока применима хотя бы одна формула, НАМ продолжает свою работу. Но нам этого не надо, поэтому мы должны принудительно остановить НАМ после этого, как он заменил первое вхождение bb. Вот для этого и нужны заключительные формулы подстановки, после применения которых НАМ останавливается. Следовательно, в нашем алгоритме обычную формулу bb -> ddd надо заменить на заключительную формулу bb |-> ddd:
Вот теперь наш алгоритм будет работать правильно:
abb c abbca -> abbabb c a -> a bb abba |-> adddabba
Слово, которое получилось после применения заключительной формулы, является выходным словом, т.е результатом применения НАМ к заданному входному слову.
Проверим наш НАМ еще и на входном слове, в которое не входит bb:
d c acb -> da c b -> dab
К последнему слову (dab) неприменима ни одна формула, поэтому, согласно определению НАМ алгоритм останавливается и это слово объявляется выходным.
Пример 2
Перестановка символов
Дан алфавит А={a,b},преобразовать P так, чтобы вначале были символы “a”, а в конце “b”.
Например: babba -> aabbb
Решение.
Казалось бы для решения этой задачи нужен сложный НАМ. Однако это не так, задача решается с помощью НАМ, содержащего всего одну формулу:
ba->ab
Пока в слове P справа хотя бы от одного символа “b” есть символ “a”, эта формула будет переносить “a” налево от этого “b”. Формула перестает работать, когда справа от “b” нет ни одного “a”, это означает, что все “a” оказались слева от b. Например:
babba -> abbba -> abbab -> ababb -> aabbb
Алгоритм остановился на последнем слове, т.к к нему уже неприменима наша формула.
Этот и предыдущий примеры показывают, что в НАМ, в отличие от машины Тьюринга, легко реализуются подстановки, вставки, и удаления символов. Однако в НАМ возникает другая проблема: как зафиксировать символ(подслово), который должен быть обработан? Рассмотрим эту проблему на следующем примере.
Пример 3 (использование спецзнака) А={а,b}. Удалить из непустого слова Р его первый символ. Пустое слово не менять.
Решение.
Ясно, что удалив первый символ слова, надо тут же остановиться. Поэтому, казалось бы, задачу решает следущий НАМ:
Однако это неправильный алгоритм, в чём можно убедиться, применив его к слову bbaba:
bb a ba |-> bbba
Как видно, этот НАМ удалил не первый символ слова, а первое вхождение символа “a”, а это разные вещи. Данный алгоритм будет правильно работать, только если входное слово начинается с символа “а”. Ясно, что перестановка формул в этом НАМ не поможет, т.к. тогда он будет, напротив, неправильно работать на словах, начинающихся с “а”.
Что делать? Надо как-то зафиксировать, пометить первый символ слова, например, поставив перед ним какой-либо знак, скажем *
отличный от символов алфавита слова. После этого уже можно с помощью формул вида *ξ|-> заменить этот знак и первый символ ξ слова на пусто и остановиться: bbaba -> *bbaba |-> baba
А как поставить * перед первым символом? Это реализуется формулой ->* с пустой левой частью, которая, по определению, приписывает свою правую часть слева к слову.
Итого, получаем следущий НАМ:
Проверим его на том же входном слове:
bbaba -> *bbaba -> **bbaba -> ***bbaba ->…
Как видно, этот алгоритм постоянно приписывает слева звёздочки. Почему? Напомним, что формула постановки с пустой левой частью применима всегда, поэтому наша формула (1) будет работать бесконечно, блокируя доступ к остальным формулам. Отсюда вытекает очень важное правило: если в НАМ есть формула с пустой левой частью (->ϐ), то её место - только в самом конце НАМ. Учтём это правило и перепишем наш НАМ
Проверим данный алгоритм:
bbaba -> *bbaba |-> baba
Казалось бы, всё в порядке. Однако это не так: наш алгоритм зациклится на пустом входном слове, т.к. постоянно будет применяться формула (3), а согласно условию задачи на таком слове НАМ должен остановиться. В чём причина этой ошибки? Дело в том, что мы ввели знак * для того, чтобы пометить первый символ слова, а затем уничтожить * и этот символ. Но в пустом слове нет ни одного символа, поэтому формулы (1) и (2) ни разу не сработают и постоянно будет выполняться формула (3). Следовательно, чтобы учесть случай пустого входного слова, надо после формул (1) и (2) записать ещё одну формулу, которая уничтожает «одинокую» звёздочку и останавливает алгоритм:
Вот теперь мы наконец-то составили правильный алгоритм.
Прежде чем перейти к следующим задачам, обобщим тот приём со звёздочкой, который мы использовали в примере 3.
Пусть в обрабатываемое слово Р входит несколько раз подслово а:
… | a | … | a | … | a | … |
и нам надо заменить одно из вхождений “а” на подслово ϐ. Такая замена делается с помощью формулы а -> ϐ. Однако, если мы применим эту формулу к слову Р, то будет заменено первое вхождение “а”. А что делать, если надо заменить какое-другое вхождение “а”, скажем второе или последнее? Так вот, чтобы на ϐ заменялось не первое вхождение а, а какое-то другое, это другое вхождение надо как-то выделить, пометить, для чего следует рядом с ним (слева или справа) поставить некоторый символ, скажем *, отличный от всех других символов, входящих в Р
… | a | … | *a | … | a | … |
Такой символ будем в дальнейшем называть спецзнаком. Его роль - выделить нужное вхождение “а” среди других, сделать его уникальным. Поскольку только около этого вхождения есть спецзнак, то надо использовать формулу *а->ϐ, чтобы заменить на ϐ именно это вхождение “а”, а не какое-то другое.
Этот приём со спецзнаком следует запомнить, т.к. в НАМ он используется очень часто.
Правда, остаётся еще одна проблема: как спецзнак разместить рядом с нужным вхождением “а”? Следующие примеры показывают, как это делается.
Пример 4 (фиксация спецзнаком заменяемого символа)
A={0,1,2,3}. Пусть Р - непустое слово. Трактуя его как запись неотрицательного целого числа в четверичной системе счисления, требуется получить запись этого же числа, но в двоичной системе.
Например: 0123 -> 00011011
Решение.
Как известно, для перевода числа из четверичной системы в двоичную надо каждую четверичную цифру заменить на пару соответствующих ей двоичных цифр: 0 -> 00, 1 -> 01, 2 -> 10, 3 -> 11. Такая замена, казалось бы, реализуется следующим НАМ:
Но этот алгоритм неправильный, в чём можно убедиться на входном слове 0123:
0 123-> 0 0123-> 0 00123->…
Ошибка здесь в том, что после замены четверичной цифры на пару двоичных цифр уже никак нельзя отличить двоичные цифры от четверичных, поэтому наш НАМ начинает заменять и двоичные цифры. Значит, надо как-то отделить ту часть числа, в которой уже была произведена замена, от той части, где замены ещё не было. Для этого предлагается пометить слева спецзнаком * ту четверичную цифру, которая сейчас должна быть заменена на пару соответствующих двоичных цифр, а после того как такая замена будет выполнена, спецзнак нужно поместить перед следующей четверичной цифрой:
0123 -> *0123 -> 00*123 -> 0001*23 -> 000110*3 -> 00011011*
Как видно, слева от спецзнака всегда находится та часть числа, которая уже переведена в двоичный вид, а справа - часть, которую ещё предстоит заменить. Поэтому никакой путаницы между четверичными и двоичными цифрами уже не будет.
Итак, спецзнак * сначала должен быть размещён слева от первой цифры четверичного числа, а затем он должен «перепрыгивать» через очередную четверичную цифру, оставляя слева от себя соответствующие ей двоичные цифры. В конце же, когда справа от * уже не окажется никакой цифры, спецзнак надо уничтожить и остановиться. Как приписать * слева к входному слову и как уничтожить спецзнак с остановом, мы уже знаем по предыдущему примеру, а вот «перепрыгивание» звёздочки реализуется с помощью формул вида *a -> ϐγ*, где а - четверичная цифра, а ϐγ - соответствующая ей пара двоичных цифр.
Итого, получаем следующий алгоритм перевода чисел из четверичной системы в двоичную
Проверим этот НАМ на входном слове 0123:
0123 -> *0 123 -> 00 *1 23 -> 0001 *2 3 -> 000110 *3 ->00011011 * |-> 00011011
Пример 5 (перемещение спецзнака)
А={а,b}. Требуется приписать символ “а” к концу слова Р. Например: bbab -> bbaba
Решение.
Прежде всего напомним, что формула ->a приписывает символ “а” слева к слову Р, а не справа. Чтобы приписать “а” справа, надо сначала пометить конец слова. Для этого воспользуемся спецзнаком, который поместим в конец Р, а затем заменим его на “а”:
P -> … -> |-> Pa
Но как поместить спецзнак в конец слова? Делается это так: сначала спецзнак * приписываем слева к слову Р, а затем «перегоняем» звёздочку через все буквы слова:
bbab -> *bbab -> b*bab -> bb*ab -> bba*b -> bbab*
А как сделать такой перегон? Нетрудно заметить, что «перепрыгивание» звёздочки через какой-то символ ξ - это замена пары * ξ на пару ξ*, которая реализуется формулой * ξ -> ξ*
С учётом всего сказанного получаем следующий НАМ:
Отметим, что при пустом входном слове этот НАМ сначала введёт звёздочку, а затем тут же заменит её на символ “а” и остановится.
Пример 6 (смена спецзнака)
А={а,b}. В слове Р заменить на аа последнее вхождение символа “а”, если такое есть. Например: bababb —> babaabb
Решение.
Удвоение символа “а” реализуется формулой a |-> аа. Но чтобы она применялась не к первому вхождению символа а, а к последнему, надо поставить, скажем, справа от последнего символа “а” спецзнак * и применить формулу а* |-> аа.
Теперь посмотрим, как поместить * рядом с последним вхождением символа “а”. Поскольку последнее вхождение - это первое вхождение от конца, то предлагается сначала приписать * слева к слову Р, затем перегнать * в конец слова (это мы уже умеем делать), а далее перегнать * справа налево через символы “b” до ближайшего символа “а”. Кроме того, надо учесть, что в Р может и не быть символа “а”; поэтому, если звёздочка снова достигнет начала слова, её надо уничтожить и остановиться.
Реализуем эту идею в виде следующего НАМ:
Здесь формула (6) приписывает * слева к входному слову Р, формулы (1) и (2) перегоняют * в конец Р, после чего формула (3) перемещает * справа налево через все b в конце слова до ближайшего, т.е. последнего, символа “а”, и, наконец, формула (4) заменяет этот символ на аа и останавливает алгоритм. Формула же (5) нужна для входных слов, в которые не входит “а”.
Проверим этот алгоритм на входном слове bababb (двойная стрелка означает несколько шагов применения формул (1) и (2)):
6 1, 2 3 2 3,2
bababb -> *bababb -> babab b* -> babab *b -> babab b* -> babab *b ->...
Как видно, вместо того, чтобы двигаться справа влево до ближайшего символа “а”, звёздочка начала «прыгать» вокруг последнего символа слова. Почему? Дело в том, что формулы (1) и (2), перегоняющие * вправо, мешают формуле (3), перегоняющей * влево. Отметим, что перестановка этих формул не поможет, т.к. тогда * начнёт «плясать» вокруг первого символа входного слова. Что делать?
Ошибка произошла из-за того, что мы используем спецзнак * в двух разных целях - как для движения вправо, так и для движения влево.
Так вот, чтобы этой ошибки не было, надо просто ввести еще один спецзнак, скажем #, распределив между этими спецзнаками обязанности: пусть * движется вправо, а # - влево. Появиться же спецзнак # должен тогда, когда * дойдет до конца слова, т.е. когда справа от * не окажется других символов. Такая замена спецзнака «исключит из игры» все формулы со звёздочкой в левой части, поэтому они уже не будут мешать формулам со спецзнаком #. Если так и сделать, то получим следущий НАМ:
Проверим этот алгоритм на прежнем входном слове:
7 1,2 3 4 4 5
bababb -> *bababb => bababb * -> babab b# -> baba b# b -> bab a# bb -> babaabb
Если же во входное слово не входит символ а, тогда имеем:
7 2 2 3 4 4 6
bb -> *b b -> b *b -> bb * -> b b# -> b# b -> #b b |-> bb
Пример 7 (перенос символа через слово) A={a,b}. Перенести в конец непустого слова Р его первый символ. Пустое слово не менять.
Например: bbaba —> babab
Решение.
Для решения этой задачи предлагается выполнить следующие действия.
1. Помечаем первый символ слова Р спецзнаком *.
2. Заменяем * и этот символ на новый символ: а на А, b на В. Этим мы фактически вводим два новых спецзнака A и B, которые нужны, чтобы отличить первый символ слова от остальных символов при его переносе в конец слова.
3. Перегоняем новый символ А или В через все символы слова Р в его конец. Такое перемещение реализуется аналогично перегону звёздочки - с помощью формул вида Аξ -> ξA и Bξ -> ξB
4. Наконец, заменяем А или В в конце слова на прежний символ (А на а, В на b) и останавливаем алгоритм.
Все эти действия реализуются в виде следующего НАМ
Здесь формулы (1) и (2) заменяют первый символ слова (вместе с *) на А или B. Формулы (3)-(6) перегоняют А и В в конец слова. Формулы (7) и (8) применяются только тогда, когда А и В окажутся в конце слова (когда за ними уже нет символов), и восстанавливают исходный вид первого символа. Формула (9) нужна на случай пустого входного слова. Формула же (10) ставит спецзнак * перед первым символом.
Проверим этот алгоритм на входном слове bаbа и на входном слове из одного символа:
10 2 6 5 6 5 8
bbaba -> * b baba -> Bb aba -> b Ba ba -> ba Bb a -> bab Ba -> babaB |-> babab
10 l 7
a -> *a -> A |-> a
Другое решение
Отметим, что в этом НАМ можно уменьшить число формул, если не
вводить новые символы А и В, а использовать вместо них пары *а и *b. Это
позволит исключить из НАМ формулы (1) и (2), которые вводят символы AиB, и формулы (7) и (8), которые восстанавливают первый символ. Что же касается «перепрыгивания» этих пар через какой-то символ то оно реализуется
формулами вида *aξ -> ξ*a и *bξ -> ξ*b. При этом никакой путаницы между
первым символом слова и остальными символами не будет, т.к. только перед первым символом находится звёздочка.
Итак, возможен и следущий НАМ, решающий нашу задачу:
Проверим этот алгоритм на прежнем входном слове bbaba:
6 4 3 4 3 5
bbaba -> *bb aba -> b *ba ba -> ba *bb a -> bab *ba -> baba *b |-> babab
Пример 8 (использование нескольких спецзнаков)
A={a,b}. Удвоить слово P т.е. приписать к Р (слева или справа) его копию. Например: abb -> abbabb
Решение.
Предлагается следующий план решения задачи:
1. Приписываем к концу слова Р символ =, справа от которого будем строить копию Р.
2. Просматриваем по очереди все символы слова Р и, не уничтожая их, переносим копию каждого символа в конец.
3. Удаляем символ =, который отделял слово Р от его копии, и останавливаем алгоритм.
Теперь уточним этот план.
Как приписать некоторый символ к концу слова, мы уже знаем: надо сначала приписать слева к слову какой-то спецзнак, скажем *, затем перегнать его направо через все символы слова и в конце, когда за * не окажется никакого символа, заменить на символ =:
abb -> *abb —> a*bb -> ab*b -> abb* —> abb=
Из предыдущего примера мы также знаем, как переносить символы слова в конец слова. Только теперь сами символы уничтожать уже не надо. Поэтому поступаем так: если надо скопировать символ а, то порождаем за ним новый символ А (заменяем а на аА),после чего этот символ А переставляем с каждым последующим символом (в том числе и с символом =), перенося тем самым А в конец слова, где и заменяем на а:
#abb= -> aAbb= -> abAb= -> abbA= -> abb=A -> abb=a Аналогично копируются и символы b.
Главный вопрос здесь: как узнать, какой именно символ исходного слова мы только что скопировали и какой символ надо копировать следующим? Для этого используем стандартный приём со спецзнаком - будем помечать новым спецзнаком # тот символ, который должен копироваться следующим (вначале это первый символ входного слова):
#abb= -> a#Abb= -> а#bАb= -> а#bbА= -> a#bb=A -> a#bb=a.Как только копия очередного символа окажется в конце, спецзнак # должен «запустить» процесс копирования следующего символа:
a#bb=a -> ab#Bb=a -> ab#bB=a -> ab#b=Ba -> ab#b=aB -> ab#b=ab ->
-> abb#B=ab -> abb#=Bab -> abb#=aBb -> abb#=abB -> abb#=abb
Когда справа от спецзнака # окажется символ =, это будет означать, что входное слово полностью скопировано. Осталось только уничтожить символы # и = после чего остановиться.
Теперь отметим, что в НАМ, реализующем такое копирование, важен взаимный порядок расположения формул (Aξ->ξA, Вξ->ξB, А->а и В->b), которые переносят символы А и В в конец и там восстанавливают символы а и b, и формулами (#а->а#А и #b->b#B), которые «вводят в игру» символы А и B. Поскольку последняя пара формул должна срабатывать только после того, как символ А или В будет полностью перенесён в конец и заменён на а или b, то эта пара формулы должна располагаться в НАМ ниже всех первых формул.
И ещё один момент. В этом НАМ используются два спецзнака * и #, первый из которых нужен для приписывания символа = справа к входному слову, а второй - для указания, какой символ слова должен копироваться следующим. Как ввести эти спецзнаки? Отметим, что использовать для этого две формулы —>* и -># нельзя, т.к. первая из них будет блокировать доступ ко второй. Оба этих спецзнака надо вводить сразу одной формулой ->#*. При этом надо учитывать, что формулы с * должны применяться самыми первыми, поэтому они должны располагаться в начале НАМ. Формулы же с #, А и В должны располагаться ниже, чтобы они работали только после того, как исчезнет * и появится символ =.
С учетом всего сказанного получаем следующий НАМ:
Здесь формулы (1)-(3) «перегоняют» звёздочку в конец входного слова и заменяют её на символ =. Формулы (4)-(7) перегоняют символ А в конец слова, после чего заменяют на a. Формулы (8)—(11) делают то же самое с В и b. Формулы (12 и (13) «вводят в игру» символы А и В, соответствующие тому символу входного слова, который должен быть скопирован следующим.
Формула (14) применяется только тогда, когда справа от # нет ни а, ни b, т.е. когда полностью просмотрено всё входное слово. И, наконец, формула (15) вводит сразу два спецзнака # и *.
Проверим данный алгоритм на двух входных словах - на пустом и на abb:
15 3 14
<пустое слово> —> # * -> #= |-> (т.е. получили <пустое слово><пустое слово>)
15 1,2 3 12 4-6 8 12
abb -> #*abb => #abb * -> #a bb= -> a#Abb= -> a#bb= A -> a #b b=a ->
12 8-10 11 12 8-10 11
-> ab#Bb= -> ab#b=a B -> ab #b =ab -> abb#B=ab -> abb#=ab B ->
11 14
->abb #= abb |-> abbabb
Другое решение
Приведём ещё одно решение задачи удвоения слова, в котором предлагается выполнить следующие действия.
1. Сначала за каждой (малой) буквой входного слова вставляем её двойник - соответствующую большую букву. Для этого приписываем слева к слову спецзнак *, а затем переносим его через каждую малую букву так, чтобы слева от него остались эта буква и её двойник. В конце слова заменяем * на новый спецзнак #, который нам ещё понадобится:
abb -> *abb -> aA*bb -> aAbB*b -> аАbВbВ* -> аАbВbВ#
2. В получившемся слове переставляем малые и большие буквы так, чтобы слева оказались все малые буквы, а справа - все большие, сохраняя при этом исходный взаимный порядок как среди малых, так и среди больших букв:
аАbВbВ# ->... -> abbABB#
3. Как видно, справа мы получили копию входного слова, но записанную большими буквами. Осталось только заменить их на малые буквы. Вот здесь-то и понадобится спецзнак #: будем перемещать его влево через каждую большую букву с заменой её на малую. Когда слева от # уже не окажется большой буквы,
надо уничтожить # и остановиться:
abbABB# -> abbAB#b -> abbA#bb -> abb#abb |-> abbabb
Все указанные действия описываются в виде следующего НАМ
2.3 Задачи для самостоятельного решения
Замечания:
1) В задачах рассматриваются только целые неотрицательные числа, если не сказано иное.
2) Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа; например:
2-> ||,5->||,0-> <пустое слово>.
2.1 A={f,h,p}. В слове Р заменить все пары ph на f
2.2 A~{f,h,p). В слове Р заменить на f только первую пару ph, если такая есть.
2.3 А={а,b,с]. Приписать слово bас слева к слову Р.
2.4 А={а,b,с]. Заменить слово Р на пустое слово, т.е. удалить из Р все символы.
2.5 А={а,b,с}. Заменить любое входное слово на слово а.
2.6 Выписать НАМ, не меняющий входное слово (при любом алфавите А).
Альтернативный алгоритм
*a->aA* Bb->bA
*b->bB* A#->#a
*-># B#->#b
Aa->aA #->|
Ab->bA ->*
Ba->aB
_bbab-> *bb ab->bB *b ab->bAbB *a b->bBbBaA *b ->bBbBaAbB * ->bBb Ba AbB#
->b Bb aBAbB#->bb Ba BAbB#->bbaB BA bB#->bbaB Bb AB#->bba Bb BAB#
->bbabBBA B# ->bbabBB A# B->bbabB B# ab - >bbab B# bab->bbab#bbab
->bbabbbab
1.Создается копия каждого символа входного слова в виде альтернативного символа
Спец.символ * помечает тот символ входного слова, который еще не имеет копии. Когда созданы все копии * меняется на #
2.Копии символов перегоняются в конец исходного слова и размещаются перед #
3.Символы-копии заменяются на исходные символы. При этом # помечает ту копию, которая еще не преобразована.
Задачи теоретического характера
Обозначения:
Последовательность из n-подряд идущих одинаковых символов. Слово в алфавите А означает, что слово состоит только из символов входного алфавита.
Если некоторый алгоритм H применим к слову P, то результат-H(P)
Применимость алгоритмов-
Алгоритм считается применимым к входному слову P если при обр. этого слова он остановится через конечное слово шагов.
Областью применимости алгоритма относительно некоторого алфавита называется множество таких слов в алфавите к которым алгоритм применим.
Пример 1
Определить область применимости НАМ относительно алфавита А={a,b}
b->b a->|b
Областью применимости алгоритма являются слова, состоящие только из символов a
a->|b b->b
Областью применимости являются все слова, содержащие хотя бы 1 символ “a” или пустое слово
Пример 2
Построить НАМ который применим ко всем словам, кроме abc
baac
#a->a#
#b->b#
*abc#->*abc#
*baac#->*baac#
*->|
->*#
Самоприменимость- применимость алгоритмов к самим себе. Это не совсем корректно т.к на вход НАМ должны подаваться линейные последовательности символов, а НАМ таковой не является.
Для применения данного алфавита к НАМ его алгоритм необходимо вывести в линию.
Запись НАМ- словоЮ состоящее из последовательно записанных формул подстановки через;
#a->a#; #b->b#;…
Тогда самоприменимость НАМ- применимость алгоритма к его записи.
Пример
1) #a-># 2) a->b
#->| b->bb
->#
Алгоритм самоприменим
#a->#; #->|; ->#; à # ->#; #->|; ->#; à ->#; #->|; #->|; ->#;
Несамоприменимый алгоритм, т.к он заканичивается
a ->b; b->bb à b ->b; b->bb à b b->b; b->bb à b bb->bb; b->bb;
Пример 3
Построить НАМ, который не самоприменим, но применим к любому слову b{a,b}
Для решения этой задачи необходимо чтобы в алгоритме команда, выполняющая замену символов, отсутствующих во входном алфавите. Тогда такой алгоритм зацикливатся на своей записи, но обраб. символы извходного алфавита
Например: *->*
Пример 4
Проблема самоприменимости алгоритмически неразрешима, т.е не существует единого алгоритма, позволяющего определить саморименим ли алгоритм. Однако в частных случаях эта задача разрешима, а именно, если алгоритм состоит из одной подстановки.
Доказательство:
Если алгоритм состоит из одной подстановки, то по его виду можно определить самоприменим ли он
£->ϐ £->|ϐ
Метод проверки самоприменимости
Если ед.форма алгоритма заключительная, то такой алгоритм всегда самоприменим. Если ед.форма алгоритма обычная, то такой алгоритм будет самоприменим, если левая часть подстановки не входит правую часть подстановки
Эквивалентность алгоритмов
Эквивалентными называются алгоритмы которые предлагают разные способы решения для одной и той же задачи, т.е для одинаковых входных слов эти алгоритмы выдают одинаковые выходные слова.
Необходимо учитывать, для оценки эквивалентности зацикливания алгоритма т.е если какой-то алгоритм зацикливается на некотором наборе слов, то эквив. след. также должен зацикливатся на таком же наборе слов.
H1(P)=H2(P)
Пример:
Являются ли эквив.
H1: a->|a
H2:a->|a
b->b
Данные алгоритмы являются эквивалентны в алгоритме A={a},но не эквивалентны в алфавите A={a,b},т.к при входном слове P= алгоритм H1 остановится(является применимым к этим словам), а алгоритм H2 зациклится
Пример
Определить эквивалентны ли следующие пары НАМ относительно A={a,b}
1) H1: a->|b H2:*b->b*
*a->|b
->*
2) H1: a->b H2: a->aa
b->a b->bb
3) H1: aa->a H2: *aa->a*
*b->b* *->|
->*<