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

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

А = {0,1,2,3,4,5,6,7,8,9}

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

Действия:

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

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

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

4. Если считана пустая ячейка то число состояло из одних 9 и заменяем S₀ на 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С

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

q₀2345

q₀ 2→ q₀Л 2q₀345

q₀3→ q₀Л 23q₀45

q₀4→ q₀Л 234q₀5

q₀5→ q₀Л 2345q₀

q₀S₀→ q₁П 234q₁5

q₁5→ q₃6С 234q₃6

Пример №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

q₀baca

q₀b→ q₂ S₀Л q₂aca

q₂a→ q₂Л aq₂ca

q₂c→ q₂Л acq₂a

q₂a→ q₂Л acaq₂

q₂ S₀→q₄bC acaq₄b

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

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

Действия:

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

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

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

	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

q₀babc

q₀b→ q₂Л bq₂abc

q₂a→ q₂Л baq₂bc

q₂b→ q₂Л babq₂c

q₂c→ q₂Л babcq₂

q₂S₀→ q₅П babq₅c

q₅c→ q₇ S₀П baq₇b

q₇b→ q₇ S₀П bq₇a

q₇a→ q₇ S₀П q₇b

q₇b→ q₇ S₀П q₇S₀

q₇S₀→ q₈C q₈S₀

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

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

Действия:

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

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

	a	b	S0
q0	q1 S0Л	q2 S0Л	q3C
q1	q3aC	q3aC	q3aC
q2	q3bC	q3bC	q3bC

q₀bab

q₀b→ q₂ S₀Л q₂ab

q₂ a→ q₃bC q₃bb

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

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

Действия:

1. Анализируем первый символ, если это а→S₀ и стоп. Если это 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

q₀baac

q₀b→ q₁ S₀Л q₁aac

q₁ a→ q₃bC q₃bac

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

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

Действия:

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

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

	a	b	c	S0
q0	q1 аП	q2 аП	q3 аП	q4C
q1	-	-	-	q4aC
q2	-	-	-	q4bC
q3	-	-	-	q4cC

q₀bbac

q₀b→ q₂ aП q₂S₀abac

q₂ S₀→ q₄bC q₄babac

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

Входной алфавит {a,b,c} в слово Р вставить а после первого вхождения символа с.

Действия:

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

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

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

	a	b	c	S0
q0	q0Л	q0Л	q1 аП	q4C
q1	q2 cП	q3 cП	-	q4cC
q2	q2П	q3 аП	-	q4aC
q3	q2 bП	q3П	-	q4bC

q₀abac

q₀a→ q₀Л aq₀bac

q₀b→ q₀Л abq₀ac

q₀a→ q₀Л abaq₀c

q₀c→ q₁аП abq₁aa

q₁a→ q₂cП aq₂bca

q₂b→ q₃аП q₃aaca

q₃a→ q₂bП q₂S₀baca

q₂S₀→ q₄aC q₄abaca

Пример №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Л

q₀cba

q₀c→ q₀Л c q₀ba

q₀b→ q₀Л cb q₀a

q₀a→ q₀Л cba q₀

q₀S₀→ q₁=П cb q₁a=

q₁a→ q₁П c q₁ba=

q₁b→ q₁П q₁cba=

q₁c→ q₁П q₁S₀cba=

q₁S₀→ q₂Л q₂cba=

q₂c→ q₄S₀Л q₄ba=

q₄b→ q₄Л b q₄a=

q₄a→ q₄Л ba q₄=

q₄=→ q₄Л ba= q₄

q₄S₀→ q₁cП ba q₁=c

q₁=→ q₁П b q₁a=c

q₁a→ q₁П q₁ba=c

q₁b→ q₁П q₁S₀ba=c

q₁S₀→ q₂Л q₂ba=c

q₂b→ q₃S₀Л q₃a=c

q₃a→ q₃Л a q₃=c

q₃=→ q₃Л a= q₃c

q₃c→ q₃Л a=c q₃

q₃S₀→ q₁bП a= q₁cb

q₁c→ q₁П a q₁=cb

q₁=→ q₁П q₁a=cb

q₁a→ q₁П q₁S₀a=cb

q₁S₀→ q₂Л q₂a=cb

q₂a→ q₂S₀Л q₂=cb

q₂=→ q₅S₀C q₅S₀cb

Пример №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Л

q₀ba

q₀b→ q₀Л bq₀a

q₀a→ q₀Л baq₀

q₀S₀→ q₁=П bq₁a=

q₁a→ q₁П q₁ba=

q₁b→ q₁П q₁S₀ba=

q₁ S₀→ q₂Л q₂ba=

q₂b→ q₄BЛ Bq₄a=

q₄a→ q₄Л Baq₄=

q₄=→ q₄Л Ba=q₄

q₄S₀→ q₁bП Baq₁=b

q₁=→ q₁П Bq₁a=b

q₁a→ q₁П q₁Ba=b

q₁B→ q₂ bЛ bq₂a=b

q₂a→ q₃AЛ bAq₃=b

q₃=→ q₃Л bA=q₃b

q₃b→ q₃Л bA=bq₃

q₃S₀→ q₁аП bA=q₁ba

q₁b→ q₁П bAq₁=ba

q₁=→ q₁П bq₁A=ba

q₁A→q₂aЛ baq₂=ba

q₂=→q₅C baq₅=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 раз, при этом заключит. состояние этой МТ "склеивается" со своим же начальным состоянием.

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