Реферат: Синтез комбинацонных схем и конечных автоматов, сети Петри
а) состояния si и sj явно различны, если соответствующие им строки в таблице выходов разные;
б) состояния si и sj явно эквивалентны, если соответствующие им строки в общей таблице переходов автомата одинаковы или становятся таковыми при замене si на sj или наоборот.
Минимизация (упрощение) автоматов основано на понятии эквивалентных автоматов. Под минимизацией автомата будем понимать сокращение числа его состояний.
2.3 Расчёты и полученные результаты.
Построение таблиц переходов, выходов и общей таблицы переходов и выходов на основе заданных уравнений автомата Мили очевидно:
|
x(j) s(j) | 0 | 1 | 2 | 3 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 2 | 1 | 0 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 |
| 4 | 1 | 0 | 1 | 0 |
| 5 | 0 | 1 | 0 | 1 |
| 6 | 1 | 0 | 1 | 0 |
| 7 | 0 | 1 | 0 | 1 |
Таблица 2.3.1 – Таблица выходов автомата
|
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 |
Таблица 2.3.4 – Таблица пар эквивалентных состояний
Ищем в полученной таблице неэквивалентные пары – пары из разных множеств. В таблице таких нет, значит, окончательно получаем автомат с двумя новыми состояниями – обозначим их 0 и 1.
Следующим шагом оформляем общую таблицу переходов для минимизированной формы автомата:
|
x(j) s(j) | 0 | 1 | 2 | 3 |
| 0 | 0/1 | 1/0 | 0/1 | 1/0 |
| 1 | 0/0 | 1/1 | 0/0 | 1/1 |
Таблица 2.3.5 – Новая общая таблица переходов.
На основании полученной общей таблицы переходов и выходов можно нарисовать граф минимизированного автомата с двумя состояниями:
0/1U 2/1 1/0 U 3/0 1/1U 3/1
0 1