А.Г. Карпов МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ СИСТЕМ Учебное методическое пособие в демо-файле для сравнения
Лабораторная работа № 1
Цель лабораторной работы освоить основные понятия теории автоматов и основные методы анализа и синтеза конечных автоматов на абстрактном уровне.
Автоматы в лабораторной работе заданы автоматной таблицей, в которой строки представляют собой состояния, а столбцы – буквы входного алфавита: на пересечении i-ой строки и j-го столбца стоит номер состояния, в которое переходит автомат из i-го состояния по j-ой входной букве, и через запятую – буква выходного алфавита, появляющаяся при этом на выходе автомата (для автоматов Мили). В таком же виде следует представлять и результаты заданий (где это необходимо).
Задание
1. Разложить заданный автомат А на автономные:
а) по входным буквам
1 2
, Ax Ax
;
б) по выходным буквам
, .
1 2
Ay Ay
2. По автомату Мили построить эквивалентный ему автомат Мура, используя теорему 4.2.2 [1].
3. По автомату Мура построить эквивалентный ему автомат Мили.
4. Найти автоматные отображения слов для заданного автомата, предполагая, что:
а) функция выхода обычная (автомат 1-го рода);
б) функция выхода сдвинутая (автомат 2-го рода).
5. Минимизировать автомат, используя алгоритм Мили.
6. Написать формулу в алгебре Клини, задающую событие в алфавите {a, b, c}.
7. Синтезировать автомат (на абстрактном уровне), представляющий регулярное событие.
8. Провести анализ автомата (написать выражение регулярного события, представляемого автоматом). Начальное состояние – 1, заключительное – 4.
Исходные данные приведены в приложении 2.