Задачи для решения.

1.Из указанного НАМ вычеркнуть ровно одну формулу подстановки так, чтобы получился алгоритм, применимый ко всем словам в алфавите {a,b}:

2 Определить область применимости указанного НАМ относительно алфавита: {a,b,с}:

3. Определить область применимости указанного НАМ относительно алфавита {a,b}:

4.Построить НАМ, который из всех слов в алфавите {a,b,c} применим только к двум словам - пустому слову и слову abccba.

5.Построить НАМ, в котором не более 5 формул подстановки и который из всех слов в алфавите {a,b} применим только к словам, имеющим следующий вид:

а) aⁿbⁿ, где n≥0 б) a"b^m, где n≠m, n≥0, m≥0

в) aⁿb^m, где n≥m≥0 г) a"b^m, где n>m≥0

6. Построить НАМ, в котором не более 5 формул подстановки и который из всех слов в алфавите {a,b,c} применим только к тем словам, длина которых:

а) кратна 5 б) не кратна 5

в) больше 4 г) меньше 4

д) равна 3 е) не равна 3

7. Построить НАМ, в котором не более 3 формул подстановки и который из всех слов в алфавите {a,b} применим только к тем словам, для которых выполняется хотя бы одно из следующих двух условий:

1) в слове меньше трёх символов a;

2) число символов b кратно 3.

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

Практическая работа №10 Самоприменимость алгоритма

Теоретические сведения:

В первом приближении самоприменимым называют алгоритм (скажем, НАМ), который применим к самому себе. Однако это некорректное опреде­ление, поскольку на вход НАМ можно подавать только слова (линейные после­довательности символов), а НАМ таковым не является. Поэтому, чтобы сделать это определение корректным, надо как-то «вытянуть» НАМ в линию. Для этого вводится понятие записи алгоритма: записью НАМ называется слово, состо­ящее из последовательно записанных через точку с запятой формул подста­новки этого алгоритма (точки с запятой отделяют друг от друга соседние фор­мулы). При этом предполагается, что точки с запятой не входят в формулы; если это не так, то вместо точки с запятой можно использовать любой другой сим­вол, не входящий в формулы.

Пусть, к примеру, имеются следующие алгоритмы H1 и H2:

H2:

Легко понять, что алгоритм однозначно определяет свою запись и наоборот. Учитывая это, а также то, что запись алгоритма является словом, которое уже можно подавать на вход алгоритму, в указанном выше определении нужно заменить фразу «применим к самому себе» на фразу «применим к своей записи». В результате получаем следующее корректное определение самопри­менимости: алгоритм называется самоприменимым, если он применим к своей записи, и несамоприменимым в противном случае.

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

Алгоритм же H2 несамоприменим, т.к. он зацикливается на своей записи:

4 5 5 5

а→b;b→bb → b→b;b→bb → bb→b; b→bb → bbb→b;b→bb →...

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

Практическая часть:

Пример 1

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

Решение

Поскольку искомый НАМ применим ко всем словам, составленным из символов a и b, то зацикливаться он может лишь на словах, содержащих какой- то дополнительный символ, скажем *. Следовательно, чтобы НАМ оказался несамоприменимым (зацикливался на своей записи), символ * должен входить в запись алгоритма (в одну из его формул) и на этом символе НАМ должен циклиться. Можно придумать много таких алгоритмов, но простейшим из них является следующий:

Пример 2

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

Доказательство

Пусть НАМ имеет вид . Тогда можно использовать

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

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

Задачи для решения.

1. Определить, самоприменим ли указанный НАМ:

2. 

2.А={a,b}. Построить НАМ, в котором не более 4 формул подстановки и который:

• самоприменим и применим ко всем словам в алфавите А;

• самоприменим, но неприменим ко всем словам в алфавите А;

• самоприменим и применим только к какому-то одному слову в алфавите А;

• самоприменим и неприменим только к какому-то одному слову в алфавите А;

• несамоприменим и неприменим ко всем словам в алфавите А;

• несамоприменим и применим только к какому-то одному слову в алфавите А;

• несамоприменим и неприменим только к какому-то одному слову в алфавите А.

3.A={a,b}. Построить НАМ, в котором не более 3 формул подстановки и который:

• самоприменим и применим только к тем словам в алфавите А, которые содержат хотя бы один символ а;

• самоприменим и неприменим только к тем словам в алфавите А, которые содержат хотя бы один символ а;

• несамоприменим и применим только к тем словам в алфавите А, которые содержат хотя бы один символ а;

• несамоприменим и неприменим только к тем словам в алфавите А, которые содержат хотя бы один символ а.

4.Пусть в некотором НАМ все формулы являются обычными и есть формула с пустой левой частью. Что можно сказать об области применимости этого НАМ? Может ли такой НАМ быть самоприменимым? (Ответ обосновать.)

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

а) самоприменимым и неприменимым ни к одному слову в алфавите {а};

б) несамоприменимым и применимым ко всем словам в алфавите {а}.

Практическая работа № 11 Эквивалентность алгоритмов.

Теоретические сведения:

Эквивалентными называются алгоритмы, которые предлагают разные способы решения одной и той же задачи. Это значит, что на одинаковых вход­ных словах они выдают одинаковые результаты (выходные слова). При этом, правда, надо учитывать и случай зацикливания: если один алгоритм зацикли­вается на каких-то входных словах, т.е. не даёт решение задачи, то и эквива­лентный ему алгоритм также не должен давать решения на этих исходных данных.

Точное определение эквивалентности алгоритмов следующее: алгоритмы H1 и H2 эквивалентны относительно алфавита A, если области примени­мости H1 и H2 относительно алфавита A совпадают и для любого слова P из этой области выполняется равенство H1(P) = H2(P).

Отметим, что в этом определении важен тот алфавит, относительно кото­рого устанавливается эквивалентность. Дело в том, что одни и те же алгоритмы могут быть эквивалентными относительно одного алфавита и не эквивалент­ными относительно другого алфавита. Например, алгоритмы

эквивалентны относительно алфавита {a} и не эквивалентны относительно алфавита {a,b}: слова в алфавите {a} они не меняют, но если в входное слово входят только символы b, то H1 остановится, а H2 зациклится.

Практическая часть:

Пример 1

Определить, эквивалентны ли следующие пары НАМ относительно алфавита {a,b}:

Решение

При проверке алгоритмов на эквивалентность надо прежде всего установить, совпадают ли области их применимости.

В случае алгоритмов Н1 и Н2, которые первое вхождение символа a заменяют на b, это условие не выполняется: Н1 применим ко всем словам из символов a и b, а Н2 зацикливается на словах, не содержащих а. Значит, алгоритмы Н1 и Н2 не эквивалентны.

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

У пары алгоритмов Н3 и Н4 одна и та же область применимости - она состоит только из одного пустого слова. На непустых же словах эти алгоритмы зацикливаются, причём зацикливаются по-разному: Н3 постоянно меняет а на b и b на а, тогда как Н4 всё время добавляет новый символ а или b. Однако такое различное поведение при зацикливании не играет никакой роли при опреде­лении эквивалентности алгоритмов. Важно лишь, чтобы в случае останова алгоритмы выдавали одинаковые выходные слова. А для пары Н3 и Н4 это условие выполняется: на единственном слове (пустом), к которому они применимы, они выдают один и тот же ответ - пустое слово. Значит, алгоритмы Н3 и Н4 эквивалентны.

Теперь рассмотрим пару алгоритмов Н5 и Н6. У них одна и та же область применимости - это множество всех слов в алфавите {α,b}. Однако второе условие эквивалентности (одинаковые результаты при одинаковых исходных данных) не выполняется. Чтобы доказать это, достаточно привести лишь одно слово, на котором алгоритмы выдают разные ответы. Таким словом может быть, например, слово аааа:

Итак, алгоритмы Н5 и Н6 не эквивалентны.

Задачи для решения

1.Для каждой указанной пары алгоритмов Н1 и Н2 определить, эквива­лентны ли они относительно алфавита {a,b}:

2.Для указанного НАМ построить такой НАМ, который эквивалентен ему относительно алфавита {a,b} и содержит только одну формулу подстановки:

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

4.Выписать программу для машины Тьюринга, эквивалентную указанному НАМ относительно алфавита {a,b}:

5. Даны следующие четыре НАМ:

Какие из этих алгоритмов эквивалентны относительно алфавита {a,b}?

Практическая работа № 12. Композиция алгоритмов.

Теоретические сведения:

Как известно, к результату одной функции можно применить другую функцию, например: sin(ctg х). Точно так же выходное слово одного алгоритма Н1 можно подать на вход другому алгоритму Н2. Такое последовательное выполнение сначала алгоритма Н1, а затем алгоритма Н2 называется композицией этих алгоритмов. При этом, правда, надо учитывать, что любой из этих алгоритмов может зацикливаться, тогда должна зацикливаться и их композиция.

Эти соображения приводят к следующему определению:

Композицией алгоритмов H1 и H2 относительно алфавита A называется такой алгоритм H (обозначается Н1°Н2 или H2(H1)), что для любого слова P в алфавите A выполняются следующие условия:

1. если Н1 неприменим к Р, то и Н неприменим к Р;

2. если Н1 применим к Р, но Н2 неприменим к слову Н1(Р), то и Н непри­меним к Р;

3. если Н1 применим к Р и Н2 применим к слову Н1(Р), то Н применим к Р, причём выполняется равенство Н(Р)=Н2(Н1(Р)).

Доказана следующая теорема: для любых нормальных алгоритмов Н1 и Н2 существует нормальный алгоритм Н, который является (относительно соответ­ствующего алфавита) композицией Н1 и Н2. (Аналогичная теорема верна и для машины Тьюринга.)

Практическая часть:

Пример 1

Построить нормальный алгоритм Н, являющийся композицией указанных нормальных алгоритмов Н1 и Н2 (Н=Н2(Н1))) относительно алфавита {a,b}:

Решение

Прежде всего отметим, что в общем случае нельзя строить композицию Н простым выписыванием друг за другом формул подстановки из алгоритмов Н1 и Н2. Например, если сначала выписать формулы из Н1, а затем из Н2, то получим алгоритм Н12, а если сначала выписать формулы из Н2, а затем из Н1, то получим алгоритм Н21:

Так вот, ни Н12, ни Н21 не является композицией алгоритмов Н1 и Н2. Например, для входного слова abb имеем:

тогда как H2(H1(abb))=H2(bb)=aa.

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

В нашем примере алгоритм Н1 удаляет из входного слова все символы a, алгоритм же Н2 заменяет все b на a. Значит, последовательное применение сначала Н1, а затем Н2 приводит к тому, что из входного слова удаляются все символы a, после чего оставшиеся символы b заменяются на a (без последу­ющего удаления их). НАМ, решающий такую задачу, может быть, например, следующим

Это и есть композиция заданных алгоритмов Н1 и Н2