double arrow

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

4

Пример №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 q3 q3 q3 q3 q3 q3 q3 q3 q2 -
q2 q3 q3 q3 q3 q3 q3 q3 q3 q3 q2 q3
q4 q4 S0Л q0Л q0Л q0Л q0Л q0Л q0Л q0Л q0Л q0Л q3

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 q1 q2 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 q3 - q4cC
q2 q2П q3 аП - q4aC
q3 q2 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Л q1 q3Л
q4 q4Л q4Л q4Л q1 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П q2 q2 q2Л q1П
q2 q3 q4 - - - q5C
q3 q3Л q3Л - - q1 q3Л
q4 q4Л q4Л - - q1 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 справа от начальной ячейки и останавливается после последней 1 в этой группе

     
 
 
 

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

     
 

-конечные

     
 

Распознавание символа

-“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* *->|

->*<


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  


4

Сейчас читают про: