Основы синтеза и диагностирования автоматов. Воронин В.В. - 190 стр.

UptoLike

ВУЗ: 

ТОГУ | Хабаровск

Составители: 

Рубрика: 

186
сократимым. Далее преобразуем таблицу переходов по правилам:
1) вычеркнуть строку, соответствующую одному из эквива-
лентных состояний (в нашем примере строку состояния 6);
2) в остальной части таблицы вычеркнутое выше
состояние следует заменить эквивалентным состояни-
ем (в нашем примере состояние 6 везде заменяем со-
стоянием 1);
3) в преобразованной таблице заменить все но-
мера состояний символами тех подмножеств, в кото-
рые они попали при 1-разбиении.
Преобразованная таблица переходов приведена в
табл. 5.12.
Далее алгоритм минимизации состоит из одно-
типных шагов. Опишем второй шаг - получить 2-
разбиение. Просматриваем табл. 5.13 и в одно под-
множество включаем те состояния, которые ранее вхо-
дили в одно
подмножество 1-разбиения, и такие, что
соответствующие им строки в модифицированной таб-
лице переходов совпадают. Получим по табл. 5.12 2-
разбиение
α
2
={0,7};
β
2
={1};
γ
2
={2};
δ
2
={3,4};
ε
2
={5}.
Произведём теперь замену номеров состояний в исходной таблице
переходов на символы подмножеств 2-разбиения (табл. 5.13). Полу-
чим в результате анализа табл. 5.13 подмножества 3-разбиения (сле-
дует проверить совпадение строк только у состояний вошедших в
одно и тоже подмножество 2-разбиения):
α
3
={0};
β
3
={1};
γ
3
={2};
δ
3
={3,4};
ε
3
={5};
φ
3
={7}.
Так как на третьем шаге получено подмножество
δ
3
, совпадаю-
щее с
δ
2
на предыдущем шаге, то оно является подмножеством экви-
валентных состояний. Остальные подмножества 3-разбиения явля-
Таблица 5.12
x
k
s
i
0 1
0
α
1
β
1
1
γ
1
α
1
2
α
1
γ
1
3
β
1
α
1
4
β
1
α
1
5
α
1
β
1
7
α
1
β
1
Таблица 5.13
x
k
s
i
0 1
0
α
2
β
2
1
γ
2
α
2
2
δ
2
γ
2
3
β
2
δ
2
4
β
2
δ
2
5
α
2
β
2
7
α
2
ε
2

Страницы