Теория автоматов и формальных языков

Теория автоматов и формальных языков

3 Задания

Задание 1: Задать два конечных автомата с 3 и 4 состояниями и двоичными входными и выходными алфавитами. Построить автомат - прямое произведение и проверить по критерию эквивалентности эквивалентность исходных автоматом между собой.

Задание 2: Для автомата с 7..9 состояний найти эквивалентный минимальный автомат. Входной и выходной алфавиты двоичные. Пожелание: чтобы автомат "хорошо" минимизировался, сначала задайте автомат с меньшим числом состояний, а затем внесите в него избыточность, чтобы получить автомат с требуемым числом состояний. Доп. работа: проверить результат по критерию эквивалентности автоматов.

Задание 3: По заданному недетерминированному автомату синтезировать детерминированный автомат-распознаватель. Вход: произвольная диаграмма 4 .. 5 вершин над двоичным алфавитом. Выход: таблица конечного автомата-распознавателя. Доп. задача - минимизировать полученный распознаватель.