 |
Минимизация частичного автомата.
|
|
|
|
Она заключается в уменьшении числа состояний путем объединения совместимых состояний.
Алгоритм минимизации:
1) Строится матрица и ищутся пары совместных состояний
2) Находим max классы совместимости, например, с помощью дерева, которое разбивает искомый алфавит состояний на основе признака несовместимости пар состояний
3) Выбирается min число классов совместимости, необходимых, но максимальных, для которых выполняется условие полноты и замкнутости. Множество классов совместимости называется полным, если каждое состоянию искомого автомата входит хотя бы в один класс совместимости. Подмножество классов допустимости называется замкнутым, если для любого класса входящего в это подмножество множество состояний следующее за этим классом целиком содержится хотя бы в одном классе совместимости тех подмножеств.
4) Проверяется полнота путем построения таблицы покрытий
5) Проверяется замкнутость путем нахождения подмножества состояний следующих за исходными классами совместимости. Это выполняется на пример с помощью дерева переходов. Если условие замкнутости не выполняется, то можно сузить классы совместимости путем удаления состояний, которые вызвали незамкнутость, при этом не должна нарушиться полнота, затем выбрать новый минимальный класс совместимости и выполнить все проверки и затем расширить число классов совместимости, добавив в них подмножество, которое получилось путем следования из исходных классов и вызвано незамкнутостью. И в первом и во втором случаях необходимо заново проверять замкнутость.
6) Каждому классу совместимости присваивается новый символ состояния.
7) Переписывается таблица переходов, причем новое состояние записывается так, чтобы не нарушилась замкнутость и склеиваются совместимые строки.
|
|
|
Пример минимизации частичного автомата:
P = {a, b, c, d, e}
S = {1, 2, 3, 4, 5, 6, 7}
W = {00, 01, 10, 11}
| Si / Pk | a | b | c | d | e |
| 1 | 1/00 | 5/*1 | --- | --- | 6/** |
| 2 | 5/*0 | 4/0* | --- | --- | --- |
| 3 | 4/11 | --- | --- | --- | 6/00 |
| 4 | 6/*1 | 6/00 | --- | 2/0* | --- |
| 5 | --- | 7/0* | --- | 4/*0 | --- |
| 6 | --- | --- | 6/*0 | --- | 2/10 |
| 7 | --- | 2/** | 1/00 | --- | --- |
Получили следующие пары совместимости:
1 ≡ 6
1 ≡ 7
2 ≡ 5
2 ≡ 6
3 ≡ 4
3 ≡ 5
3 ≡ 7
4 ≡ 6
4 ≡ 7
5 ≡ 6
Строим дерево классов:
C1 = {1, 6}
C2 = {1, 7}
C3 = {2, 5, 6}
C4 = {3, 4, 7}
C5 = {3, 5}
C6 = {3, 6}
Выбираем множество классов C1, C3, C4, C6
В зависимости от того какие новые состояния мы припишем старому мы получаем разные автоматы, но все они будут иметь одинаковое количество состояний.
Абстрактный этап синтеза конечного автомат. (неканонический метод).
Примером неканонического синтеза является построение микропрограммного автомата. Микропрограммным автоматом будем показывать автомат реализующий заданную микропрограмму. Все свои области применения микропрограммного автомата можно рассматривать как абстрактный автомат с закодированными входными и выходными словами и абстрактными состояниями.
Алгоритм перехода от граф схемы микропрограммы к автомату Мура.
- Начальная и конечная вершины помечаются начальным состоянием.
- Все операторные вершины граф-схемы помечаются индивидуальными символами состояний автомата, в независимости от микропрограмм находящихся в этих вершинах.
- Строится n+1 вершина графа(n – число операторных вершин в алгоритме), каждая вершина помечается символом состояния и микрокомандой из операторной вершины в качестве выходного сигнала.
- Вершину Si соединяем с Sj дугой на которой в качестве входного сигнала приводят код логического условия, которые допускают переход из оператора помеченного Si в оператор помеченный Sj.
Пример:
|
|
|
P = {P0, P1, P2, P3}
S = {S0, S1, S2, S3, S4}
W = { W0, W1, W2, W3}
Автомат полностью определен, следовательно перейдем к автомату Мили:
Учет взаимодействия проекционного и управляющего автоматов.
Алгоритм получения.
При переходе в граф-схеме алгоритма мы получаем полностью определенный автомат, т.е. из каждого состояния существуют переходы по любой комбинации логических условий, однако существуют взаимосвязи между микрооперациями, которые являются выходными сигналами автомата и логическими условиями, которые являются входными сигналами автомата.
С другой стороны наличие прочерков в таблице переходов частичного автомата может позволить получить более компактный автомат после минимизации.
Следовательно имея два автомата: частичный и полностью определенный, описывающий по одному алгоритму которого необходимо выбирать частичный в качестве окончательного, чтобы упростить (уменьшить затраты на автомат, сократить число состояний).
Для построения частичного автомата необходимо получить наборы X возможных в каждом состоянии. Для этого необходимо знать:
1) Множество наборов X, которые может получить автомат на вход, когда он находится в начальном состоянии S0 – будем обозначать U0
2) Как каждая микрооперация влияет на значение логических условий.
|
|
|
