Студентам > Курсовые > Синтез комбинацонных схем и конечных автоматов
Синтез комбинацонных схем и конечных автоматовСтраница: 5/10
Таблица 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
|
| 
Главная
Документация
Файлы
Информация
