Быстрый поиск

Реферат: Синтез комбинацонных схем и конечных автоматов, сети Петри

x(j) s(j)	0	1	2	3
0	0	1	2	3
1	2	3	4	5
2	4	5	6	7
3	6	7	0	1
4	0	1	2	3
5	2	3	4	5
6	4	5	6	7
7	6	7	0	1

Таблица 2.3.2 – Таблица переходов автомата

x(j) s(j)	0	1	2	3
0	0/1	1/0	2/1	3/0
1	2/0	3/1	4/0	5/1
2	4/1	5/0	6/1	7/0
3	6/0	7/1	0/0	1/1
4	0/1	1/0	2/1	3/0
5	2/0	3/1	4/0	5/1
6	4/1	5/0	6/1	7/0
7	6/0	7/1	0/0	1/1

Таблица 2.3.3 – Общая таблица переходов и выходов автомата

Перейдём непосредственно к минимизации полученного автомата по числу состояний. Для этого воспользуемся алгоритмом, известным в литературе как метод Гриса - Хопкрофта. Его достоинство в том, что он даёт гарантированно минимальную форму автомата. Однако в общем случае он является довольно трудоёмким и применяется, как правило, для автоматов с небольшим количеством состояний. Он основан на свойстве транзитивности эквивалентности

(si ~ sj) ∩ (sj ~ sk) (si ~ sk) (2.3.1)

Пара эквивалентных состояний переходит при всех возможных значениях входа в пары также эквивалентных состояний.

Алгоритм состоит из следующих шагов.

Сначала разбиваем все состояния автомата на множества по признаку совпадения выходных сигналов. В нашем случае получаем 2 множества: S1 = {0, 2, 4, 6} и S2 = {1, 3, 5, 7}.

Чтобы назвать каждый из полученных классов новым состоянием, нужно убедиться в том, что в каждый класс входят только эквивалентные между собой состояния. Для этого составляем таблицу пар эквивалентных состояний. При этом не забываем о том, что эквивалентными могут быть состояния, принадлежащие только одному классу. В таблицу заносим все те пары, в которые переходят при соответствующих входах исходные, вероятно эквивалентные, пары:

пары	0	1	2	3
0;2	0;4	1;5	2;6	3;7
0;4	0;0	1;1	2;2	3;3
0;6	0;4	1;5	2;6	3;7
2;4	4;0	5;1	6;2	3;7
2;6	4;4	5;5	6;6	7;7
4;6	0;4	1;5	2;6	3;7
1;3	2;6	3;7	4;0	5;1
1;5	2;2	3;3	4;4	5;5
1;7	2;6	3;7	4;0	5;1
3;5	6;2	7;3	0;4	1;5
3;7	6;6	7;7	0;0	1;1
5;7	2;6	3;7	4;0	5;1