mlaat_ri (Выполненное дз по теории алгоритмов вариант 5 (см условие))
Описание файла
PDF-файл из архива "Выполненное дз по теории алгоритмов вариант 5 (см условие)", который расположен в категории "". Всё это находится в предмете "математическая логика и теория алгоритмов" из 4 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Федеральное Государственное Бюджетное ОбщеобразовательноеУчреждение Высшего ОбразованияМосковский государственный технический университетимени Н. Э. Баумана(Национальный Исследовательский Университет) ФакультетИУ «Информатика и системы управления»Кафедра ИУ3 «Информационные системы и телекоммуникации»Модульное Домашнее задание по дисциплине“Теория алгоритмов”Вариант № 5Группа ИУ3-41БВыполнил: Темури К.Проверил: Стырт О.
Г.Москва, 2020Постановка задачиИспользуя теоремы сочетания применительно к МТ, построить МТ,выполняющей умножение натуральных чисел, представленных словами валфавите 0 = {0,1}(именно, натуральное число n записывается как слово 011…1 - с n единицами).Введем новые символы, которые не принадлежат искомому алфавиту,тем самым дополнив искомый алфавит:При этом {,,{,,,где {, ,обозначение пустой клеткиПусть на вход поступает слово вида:0 11⏟ … 1 0 11⏟ … 1 =где , Тогда искомый алгорифм будет выглядеть следующим образом:000 → 0020 → 2030 → 3040 → 4050 → 50101 → 0121 → 2131 → 3141 → 551 → 51x0 → 02 → 23 → 4=0 = → 1 = 2 =→ 2 = 5 → 65 =→ 5 = 5 → 5aS0 → 010 → 20060 → 9070 → 70161 → 771 → 71x7 → 7=7 =→ 7 = aS61 → 62 → 390 → 90100 → 100110 → 110101 → 59 → 1011 → ′10 =→ 11 = 7 → 77 → 813 → 39 → 918 → 510 → 1011 → 111Описание состояний:Начальное состояние. Ищем "=" справа.
При нахождениипереходим в состояние 1Заменяем "S" на "0" и переходим в состояние 2Ищем "S" слева. При нахождении переходим в состояние3Ищем "x" справа. При нахождении переходим в состояние4Заменяем "1" на "a" и переходим в состояние 5Ищем "x" слева. При нахождении переходим в состояние6Ищем "1" слева, заменяем её на "а" и переходим всостояние 7.В случае если "1" закончились, находим "0" и переходимв состояние 9Переходим в конец (ищем "S" справа), заменяем "S" на"1" и переходим в состояние 8Добавляем "S" в конец и переходим в состояние 5Ищем "x" справа и переходим в состояние10.
Пока ищем заменяем "а" на "1"Ищем "1" или "=" справа. При нахождении "1" заменяемна "а" и переходим в состояние 5При нахождении "=" переходим в состояние 11Ищем "x" слева. При нахождении переходим всостояние ′ . Пока ищем заменяем "а" на "1"Остановка алгоритма′На выходе слово вида:0 11 … 1 0 11⏟ … 1 = 0 1 11 … 1 ⏟1 11… 11ый 2й…1ый11 … 1где , ∈ ℕРис. 1 Пример реализации программы в эмуляторе МТ.Указатель стоит перед 1-ой буквой словаРис. 2 Завершение программы в эмуляторе МТ.Ответ на выходе получился правильный..
