Математические основы теории систем

Автоматы в лабораторной работе заданы автоматной таблицей, в которой строки представляют собой состояния, а столбцы – буквы входного алфавита: на пересечении i-ой строки и j-го столбца стоит номер состояния, в которое переходит автомат из i-го состояния по j-ой входной букве, и через запятую – буква выходного алфавита, появляющаяся при этом на выходе автомата (для автоматов Мили). В таком же виде следует представлять и результаты заданий (где это необходимо).
Задание:
1. Разложить заданный автомат А на автономные:
а) по входным буквам A_x1, A_x2;
б) по выходным буквам A_y1, A_y2;
2. По автомату Мили построить эквивалентный ему автомат Мура, используя теорему 4.2.2.
3. По автомату Мура построить эквивалентный ему автомат Мили.
4. Найти автоматные отображения слов для заданного автомата, предполагая, что:
а) функция выхода обычная (автомат 1-го рода);
б) функция выхода сдвинутая (автомат 2-го рода).
5. Минимизировать автомат, используя алгоритм Мили.
6. Написать формулу в алгебре Клини, задающую событие в алфавите {a, b, c}.
7. Синтезировать автомат (на абстрактном уровне), представляющий регулярное событие.
8. Провести анализ автомата (написать выражение регулярного события, представляемого автоматом). Начальное состояние – 1, заключительное – 4.

qi/xj x1 x2
1 3,y1 3,y2
2 1,y2 3,y1
3 2,y1 1,y1

q i/xj x1 x2
1 1,y4 2,y1
2 2,y3 2,y2
По автомату Мура построить эквивалентный ему автомат Мили.
q /x x1 x2 µ
1 2 4 y2
2 3 2 y3
3 1 3 y1
4 2 1 y2
4. Найти автоматные отображения слов для заданного автомата, предполагая, что:
а) функция выхода обычная (автомат 1-го рода);
б) функция выхода сдвинутая (автомат 2-го рода).
qi/xj x1 x2 x3 qi/xj
1 2, y2 2, y1 3, y1 1
2 3, y2 1, y1 4, y2 2
3 2, y2 1, y2 4, y1 3
x = x1x3x2x1x2x1x3
5. Минимизировать автомат, используя алгоритм Мили.
qi/xj x1 x2 x3
1 8,1 7,1 1,0
2 2,0 6,1 2,1
3 9,0 5,1 5,1
4 8,1 5,1 1,0
5 7,1 8,0 3,0
6 5,1 5,0 2,0
7 7,1 7,0 3,0
8 4,0 7,1 7,1
9 4,0 6,1 8,1
6. Написать формулу в алгебре Клини, задающую событие в алфавите {a, b, c}. Все слова, начинающиеся на ac и не заканчивающиеся на b.
7. Синтезировать автомат (на абстрактном уровне), представляющий регулярное событие.
(a  c) (b  c)* a*
8. Провести анализ автомата (написать выражение регулярного события, представляемого автоматом). Начальное состояние – 1, заключительное – 4
a b c
1 3 1 4
2 4 3 -
3 3 2 4
4 4 - -