В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая - Машина Тьюринга и алгоритмы Маркова. Решение задач (1000390), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

Что можно сказать об области применимости этогоНАМ? Может ли такой НАМ быть самоприменимым? (Ответ обосновать.)3.13 Пусть в левых и правых частях всех формул подстановки некоторого НАМиспользуются только символы a. Установить, может ли такой НАМ быть:а) самоприменимым и неприменимым ни к одному слову в алфавите {a};б) несамоприменимым и применимым ко всем словам в алфавите {a}.3.14 Для каждой указанной пары алгоритмов Н1 и Н2 определить, эквивалентны ли они относительно алфавита {a,b}:а) Н1:{a →a⎧ * a → aaН2: ⎨⎩ a →*a44⎧ ba → abб) Н1: ⎨⎩ ab →в) Н1:г) Н1:⎧ ab →Н2: ⎨⎩ ba →{ ab →⎧ * ab⎪ *a⎪Н2: ⎨ * b⎪*⎪⎩→*→ a*→ b*a→*{ ab →⎧ * ab⎪ *a⎪Н2: ⎨ * b⎪*⎪⎩→→ a*→ b*a→*⎧ * a → a#⎪ *b → b *⎧ *b → b *⎪⎪ # a a⎪ *a aд) Н1: ⎨Н2: ⎨#b → b ** a⎪⎪aa→a*#⎩⎪⎪⎩→*3.15 Для указанного НАМ построить такой НАМ, который эквивалентен емуотносительно алфавита {a,b} и содержит только одну формулу подстановки:⎧ +a→a+⎪ +b →b+⎧ *a → b*⎧ *a →*⎪ + →*⎪ *b → b*⎪ *b → b*⎪б) ⎨а) ⎨ a * → * aв) ⎨* a* →⎪⎪⎪ b * → *b→*→*⎩⎩⎪* aa⎪→+⎩3.16 Из следующего НАМ вычеркнуть как можно больше правил так, чтобыполучившийся алгоритм был эквивалентен ему относительно алфавита {a,b}:⎧ aba → aab⎪ ba→ ab⎨ abab → aabb⎪→⎩ ab3.17 Выписать программу для машины Тьюринга, эквивалентную указанномуНАМ относительно алфавита {a,b}:⎧ ab a ab⎪а) ⎨ ba a ba⎪⎩→⎧ aa → aaб) ⎨⎩ bb → bb⎧ *a → b*⎪в) ⎨ * b a b⎪⎩→*3.18 Даны следующие четыре НАМ:⎧ aa → aН1: ⎨⎩ ab a abc⎧ aa → aН2: ⎨⎩ ab → abd⎧ aa → aН3: ⎨⎩ ab → ab45⎧ aa → a⎪Н4: ⎨ ab → abd⎪⎩ d aКакие из этих алгоритмов эквивалентны относительно алфавита {a,b}?3.19 Для каждой пары алгоритмов Н1 и Н2 построить их композициюотносительно алфавита {a,b} в виде нормального алгоритма Н (Н=Н2(Н1)):{ ba →б) Н1: { ab → baа) Н1:Н2:Н2:{ a → bb{ b→a⎧ * a →b *⎪ *b →a *Н2: { ab →в) Н1: ⎨* a⎪→*⎩3.20 Заданы следующие три НАМ:⎧ ca → acН: ⎨⎩ cb → bcЯвляется ли алгоритм Н композицией алгоритмов Н1 и Н2 (Н=Н2(Н1))относительно алфавита {a,b,c}? Ответ обосновать.Н1:{ ca → acН2:{ cb→ bc3.21 Имеются следующие пять НАМ:⎧ *b →a *⎪ *a → a*⎪⎧ ab →Н5: ⎨ * aН1: { ab → Н2: { b → a Н3: ⎨b→a⎩⎪ ab →⎪→*⎩Определить, есть ли среди этих алгоритмов такие, которые являются композицией других.

Если да, то указать все такие композиции.⎧ ab⎪bН4: ⎨⎪⎩*46→→a→*aРекомендуемая литература1. Э.З. Любимский, В.В. Мартынюк, Н.П. Трифонов. Программирование. –М., “Наука”, 1980.2. Л.С. Корухова, М.Р. Шура-Бура. Введение в алгоритмы (учебное пособиедля студентов 1 курса) – М., Издательский отдел факультета ВМК МГУ, 1997.3. А.А. Марков, Н.М. Нагорный.

Теория алгорифмов. – М., ФАЗИС, 1996.Содержание1. Машина Тьюринга ............................................................................................31.1 Краткое описание машины Тьюринга ............................................................31.2 Примеры на составление программ для МТ ...................................................71.3 Задачи для самостоятельного решения..........................................................152. Нормальные алгоритмы Маркова .............................................................182.1 Краткое описание нормальных алгоритмов Маркова ..................................192.2 Примеры на составление НАМ ......................................................................212.3 Задачи для самостоятельного решения..........................................................323.

Задачи теоретического характера .............................................................363.1 Применимость алгоритма ..............................................................................363.2 Самоприменимость алгоритма ......................................................................383.3 Эквивалентность алгоритмов ........................................................................403.4 Композиция алгоритмов.................................................................................413.5 Задачи для самостоятельного решения..........................................................4347.

Характеристики

Список файлов книги