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

Правила оформления решений к задачам остаются прежними (из домашнего задания 1). Если для автомата не указан алфавит X, то подразумевается {0, 1}.

Часть 1. Синтез автоматов

  1. Постройте детерминированный автомат-распознаватель для языка из слов, содержащих три подряд нуля. Продемонстрируйте работу полученного автомата на словах: 010001, 0010.
  2. Постройте детерминированный автомат-распознаватель для языка из слов, которые начинаются или оканчиваются (или и то, и другое одновременно) на 01. Продемонстрируйте работу полученного автомата на словах: 11101, 0100, 00100.
  3. Постройте недетерминированный автомат-распознаватель для языка из слов, заканчивающихся на 1. Указание: граф переходов должен иметь не более двух дуг (не считая «дугу без начала» для обозначения стартового состояния). Продемонстрируйте работу полученного автомата на словах: 11101, 0010. В ходе демонстрации должно быть видно ветвление в состояниях.
  4. Рассмотрим модификацию НКАР, в которой на дуге перехода автомата вместо буквы из множества разрешается указывать  символ ε. По таким ε-дугам автомат может совершать переход во время работы, не читая символа с входной ленты. Постройте недетерминированный автомат-распознаватель с ε-дугами для языка из слов, которые содержат чётное количество 0 или чётное количество 1. Указание: на первом шаге работы автомат с помощью ε-переходов спонтанно решает, какое слово перед ним: с чётным количеством 0 или 1. Продемонстрируйте работу полученного автомата на словах: 1110, 00100, 11.
  5. Постройте недетерминированный автомат-распознаватель для языка из слов, представляющих десятичную запись чисел, делящихся на 4. Продемонстрируйте работу полученного автомата на словах: 1234, 4320.
  6. Постройте недетерминированный автомат-распознаватель для языка над алфавитом {0, 1, . . . , 9} из слов, в которых крайняя справа цифра больше нигде в них не встречается (чтение происходит, как обычно, слева направо). Продемонстрируйте работу полученного автомата на словах: 1234, 4323.

Часть 2. Детерминизация

Проведите детерминизацию следующих автоматов. Приведите пример работы каждого результирующего автомата на словах длины 4–5 символов, которые он допускает и которые он отвергает.

Часть 3. Минимизация

Составить таблицу различимости состояний и провести минимизацию следующих автоматов (звёздочкой обозначены допускающие состояния). Привести примеры работы каждого результирующего автомата на словах длины 4–5 символов, которые допускается, а также и которые отвергаются. Попытайтесь с помощью примеров продемонстрировать выигрыш от минимизации автомата.

Дедлайны

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

На занятии 21 октября ожидается разбор задач: студентам будет предложено продемонстрировать свои решения.