Методы абстрактного синтеза
Пусть есть автомат, заданный следующей отмеченной таблицей переходов:
|
yg |
y1 |
y1 |
y1 |
y2 |
y1 |
y2 |
y2 |
y2 |
|
xj\ai |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
x1 |
2 |
5 |
2 |
2 |
4 |
4 |
5 |
2 |
|
x2 |
3 |
1 |
7 |
3 |
5 |
5 |
1 |
7 |
|
x3 |
1 |
6 |
1 |
1 |
1 |
1 |
6 |
1 |
Алгоритм минимизации заключается в следующем:
1. Все внутренние разбиваются на группы по числу выходных сигналов. В нашем случае есть два выходных сигнала y1 и y1 и следовательно будет две группы, которые мы обозначим буквами a и b.
2. По таблице переходов автомата определяют, к каким группам принадлежат внутренние состояния, в которые автомат из данного состояния под воздействием каждой буквы входного алфавита. Эти состояния запишем в виде последовательности букв под каждым из состояний автомата. Например, из состояния 0 автомат переходит в состояния 2, 3 и 1, которые принадлежат соответственно к следующим группам a, b и a. Эта последовательность букв (aba) и записывается под состоянием 0.
3. Проводят новое разделение внутренних состояний на группы, объединяя в каждой группе состояния, отмеченные одинаковой последовательностью букв. В нашем случае каждая из двух групп распадается на две группы, по числу различных последовательностей букв.
предыдущаяследующая