Домашнее задание 1

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

Слова «спроектировать автомат» всегда означают, что следует явно выписать все компоненты определения автомата-преобразователя (Q, X, Y, δ, f) и нарисовать диаграмму (граф) переходов. Если явно не указан тип автомата (машина Мили или Мура), то выбор следует сделать самостоятельно (произвольно). Если из задачи не следует или явно не указано иное, предполагается работа с бинарными алфавитами (X = Y = {0, 1}).

  1. Построить машину Мили, который выводит 1, если встречен перепад сигналов (во входном потоке встретились последовательно 01 или 10), и выводит 0 в противном случае. Пример: для входной последовательности 00100 выход должен быть 00110.
  2. Преобразовать машину Мили из задачи 1 в машину Мура.
  3. Построить машину Мура для моделирования следующего процесса. Монета многократно подбрасывается и делаются одни отметки при чётных выпадениях решки (номинала) подряд и другие отметки при каждом третьем выпадении орла необязательно подряд.
  4. Преобразовать машину Мура из задачи 3 в машину Мили. Замечание: если в задаче 3 не удалось построить машину Мура, то можно сразу построить машину Мили и преобразовать её в машину Мура, но с потерей части балла.
  5. Модифицировать пример «Турникет» из лекции следующим образом. Если в закрытый турникет пытаются дважды пройти без оплаты, он ломается (отдельное состояние). В этой ситуации турникет не сможет больше вернуться ни в одно из двух корректных состояний, его выходной сигнал должен быть особым (не совпадать с имеющимися двумя) — можно считать, что этот сигнал соответствует мигающим лампочкам. Если в закрытый турникет попытались пройти лишь один раз, а потом всё же бросили монету, он ведёт себя как обычно (переходит в открытое состояние и зажигает зелёную лампочку). Выписать алфавиты, диаграмму (граф) переходов полученного автомата, а также таблицы функций f и δ.
  6. Спроектировать автомат, который складывает по два числа, записанных на ленте в троичной системе счисления, по аналогии с примером двоичного сумматора из лекции или формально доказать, что такового не существует. В первом случае продемонстрировать работу автомата на двух произвольных словых из пяти троичных разрядов: в одном случае, когда есть перенос из старшего разряда, в другом — когда нет. В первом примере указать, какие ограничения накладываются на вход.
  7. Спроектировать автомат, который складывает по три двоичных числа, записанных на ленте, по аналогии с примером двоичного сумматора из лекции или формально доказать, что такового не существует. В первом случае продемонстрировать работу автомата на произвольном слове из пяти троек двоичных разрядов.
  8. Спроектировать автомат, вычисляющий максимум из двух двоичных чисел или доказать, что такового не существует. Числа читаются, начиная со старших разрядов. Считать, что более кроткое число добито нулями до длины более длинного. Продемонстрировать работу автомата на двух словах по пять двоек двоичных разрядов каждое.

Дедлайны

  • Мягкий дедлайн (до него возможно получить полный балл): 6 октября, 23:00.
  • Жёсткий дедлайн (до него возможно получить лишь половину балла): 13 октября, 23:00.

На занятии 7 октября ожидается защита работ: каждый студент должен будет презентовать решение одной из задач ДЗ у доски, чтобы получить полный балл.