- •Проектирование автоматов
- •Проектирование автоматов
- •5.7. Упражнения 90
- •Введение
- •1. Абстрактные автоматы
- •1.1. Эквивалентность автоматов
- •1.2. Минимизация автоматов
- •1.2.1. Минимизация полностью определенного автомата
- •1.2.2. Минимизация частичного автомата
- •1.3. Композиция автоматов
- •1.3.1. Параллельное соединение
- •1.3.2. Последовательное соединение
- •1.3.3. Соединение с обратной связью
- •1.3.4. Соединение в сеть
- •1.4 Декомпозиция автомата
- •1.4.1. Задача декомпозиции
- •1.4.2. Разбиения со свойствами подстановки
- •1.4.3. Метод декомпозиции
- •1.5. Упражнения Эквивалентность автоматов
- •Минимизация полностью определённого автомата.
- •Декомпозиция автоматов
- •2. Структурные автоматы
- •2.1. Автоматная полнота и теорема в.М.Глушкова
- •2.2. Гонки в автомате
- •2.2.1. Кодирование состояний
- •2.2.2. Понятие о гонках. Противогоночное кодирование
- •2.3. Проектирование автомата
- •2.4. Упражнение Кодирование
- •Синтез автомата
- •3. Синтез схем
- •3.1. Определения
- •3.2. Функциональная полнота базиса
- •3.2.1. Классы функций
- •3.2.2. Монотонные функции
- •3.2.3. Самодвойственные функции
- •3.2.4. Линейные функции
- •3.2.5. Функции, сохраняющие константу
- •3.2.6. Функциональная полнота
- •3.3. Топологические ограничения в схемах
- •3.3.1. Плоские схемы
- •3.3.2. Ограничения на глубину связи в схеме
- •3.4. Методы синтеза схем
- •3.4.1. Метод факторизации
- •3.4.2. Метод декомпозиции
- •3.4.3. Синтез схем в классическом базисе.
- •3.4.4. Синтез схем в монофункциональном базисе.
- •3.5. Упражнения Функциональная полнота
- •Синтез схем
- •4. Эксперименты над автоматами
- •4.1. Построение диагностических деревьев
- •4.2. Диагностические и установочные эксперименты
- •4.2.1. Дерево преемников
- •4.2.2. Диагностический эксперимент
- •4.2.3. Установочный эксперимент
- •4.3. Упражнения Диагностические эксперименты
- •Установочные эксперименты
- •5. Формальные грамматики
- •5.1. Языки и порождающие их грамматики
- •5.2. Примеры фрагментов описаний в языках программирования.
- •5.3. Порождающая грамматика
- •5.4. Классы языков и грамматик
- •5.5. Язык, понимаемый устройством
- •5.6. Автоматные языки
- •5.7. Упражнения
- •Библиографический список
- •Проектирование автоматов
- •620002, Екатеринбург, Мира, 19
1.2.2. Минимизация частичного автомата
Определение. Частичным (не полностью определенным) авто-матом называют автомат, у которого и/или определены не полно-стью, значит, у него входные слова могут быть допустимыми и недопус-тимыми. Слово допустимо в состоянии a, если для него возможно опре-делить соответствующее ему выходное слово. Иначе слово будем считать недопустимым в состоянии a.
Определение. Два состояния автомата am и an называются со-вместимыми, что обозначим как am ~an , если при подаче произвольного слова на вход автомата, который находится в состоянии am, и в тот же автомат, но в состоянии an, на выходе получаются непротиворечивые слова, то есть совпадающие там, где оба определены.
Свойства совместимости состояний.
am ~ am (рефлексивность),
a m ~ an => an ~ am (симметричность),
am ~ ak & an ~ ak am ~ an (нет транзитивности ).
Два состояния am и an совместимы, , если для любого zi Z, где функции определены, выполняются два условия:
(am,zi) ~ (an,zi) (условие совместимости по переходу),
(am,zi) = (an,zi) (условие совместимости по выходу).
Определение. Классом совместимости состояний C называют множество состояний, все элементы которого попарно совместимы друг с другом.
Классы совместимости могут пересекаться (в отличие от классов эквивалентности).
Класс совместимости назовём максимальным, если он не содержится полностью в другом классе.
Классом совместимости также является класс B = (C, z), если С - класс совместимости.
Автоматы S1 = <Z1, W1, A1, 1, 1> и S = <Z, W, A, , > изоморфны, если они отличаются только именами входов, выходов и состояний.
Говорят, что автомат S1 = <Z1, W1, A1, 1, 1> является подавтоматом автомата S = <Z,W,A,,>, если Z Z1, W W1, A A1, и функции переходов и выходов автоматов совпадают на множествах Z, W, A. (автомат S1 делает всё то же, что и автомат S, и может быть что-то еще).
Автомат S1 = <Z1, W1, A1, 1, 1> покрывает (реализует) автомат S= <Z,W,A,,>, если он содержит подавтомат S2, который с точностью до имен состояний совпадает с автоматом, покрывающим автомат S, т.е. найдётся подавтомат, изоморфный S.
Алгоритм Ангера - Полла
Для инициального автомата первым шагом минимизации автомата должно быть удаление недостижимых состояний, т.е. состояний, в которые автомат не может перейти из начального состояния ни при каких входных словах.
Далее процесс минимизации частичных автоматов включает в себя три основных этапа:
нахождение всех максимальных классов совместимости;
нахождение минимального замкнутого покрытия;
получение по минимальному замкнутому покрытию автомата.
Первый этап.
Рассмотрим алгоритм получения совместимых пар с помощью треугольной таблицы, предложенный М. Поллом и С. Ангером. Рассматривать будем на примере автомата, заданного таблицами переходов и выходов, приведёнными в табл.1.10 и 1.11:
По таблицам переходов и выходов автомата составляется тре-угольная таблица, столбцы и строки которой сопоставляются с состоя-ниями автомата. Вид таблицы обусловлен рефлексивностью и симмет-ричностью отношения совместимости состояний - она треугольная. Для упрощения записи в этой таблице вместо ai будем писать i.
В треугольной таблице на пересечении строки m и столбца s ставятся:
–Х (крест), если состояния am и as несовместимы по выходу, например а2 и а5 (в таблице выходов в строке Z3 в столбцах a2 и а5 стоят разные выходные сигналы - w1 и w2 соответственно).
–Множество всех пар состояний, следующих за парой (am, as) и отличных от неё, - все те пары, совместимость которых необходима для совместимости пары (am, as) по условию совместимости по переходу.
Таблица 1.10 |
|||||||||||||
|
a1 |
a2 |
a3 |
a4 |
a5 |
||||||||
z1 |
a2 |
a3 |
a3 |
-- |
-- |
||||||||
z2 |
-- |
a5 |
a4 |
a1 |
-- |
||||||||
z3 |
a3 |
a2 |
-- |
a2 |
a1 |
||||||||
z4 |
a2 |
-- |
a5 |
-- |
-- |
||||||||
Таблица 1.11 |
|
||||||||||||
|
a1 |
a2 |
a3 |
a4 |
a5 |
|
|||||||
z1 |
w1 |
w1 |
w1 |
-- |
-- |
|
|||||||
z2 |
w2 |
w2 |
w2 |
w2 |
-- |
|
|||||||
z3 |
-- |
w1 |
-- |
-- |
w2 |
|
|||||||
z4 |
w1 |
-- |
w1 |
-- |
-- |
|
–V (птичка), если за (аm, аs) не следуют пары, отличные от (аm, аs), т.е. пара (аm, аs) совместима без дополни-тельных условий, налагае-мых на совместимость дру-гих пар. В нашем примере это пара (а3, а5).
Таблица 1.12 |
||||
a2 |
2.3 |
|
|
|
a3 |
2.3 2.5 |
4.5 |
|
|
a4 |
2.3 |
1.5 |
1.4 |
|
a5 |
1.3 |
X |
V |
1.2 |
|
a1 |
a2 |
a3 |
a4 |
Таблица 1.13 |
||||
a2 |
2.3 |
|
|
|
a3 |
2.3X 2.5X |
4.5 |
|
|
a4 |
2.3 |
1.5XX |
1.4 |
|
a5 |
1.3XX |
XX |
V |
1.2 |
|
a1 |
a2 |
a3 |
a4 |
(1, 5), (2, 4), (2, 5) не совместимы.
Будем говорить, что множество состояний В (В А) совместимо с состоянием am A (обозначение am~В), если am ~ as для любого asВ. Рассмотрим способ нахождения максимальных классов совместимости из совместимых пар.
Алгоритм нахождения всех максимальных классов совместимости сводится к следующему:
Начинаем составление списка Ф классов совместимости с совместимых пар в крайнем правом столбце таблицы, имеющем, по крайней мере, одну клетку без крестов. В примере Ф = {{4, 5}}.
Продвигаясь влево, записываем для каждого i-го столбца множество состояний Аi ~ ai, т.е. множество всех состояний, соответствующих клеткам без крестов в i-м столбце таблицы.
В нашем примере 3~{4,5} (в третьем столбце таблицы нет крестов в строках 4 и 5).
Каждое Аi пересекаем с каждым членом текущего списка Ф. У нас
А3 = {4, 5} и список Ф также содержит единственный элемент {4, 5}:
{4,5}{4,5} = {4,5}.
Если такое пересечение содержит более одного состояния, то добавляем в список объединение {ai} с результатом пересечения:
{3}{4,5} = {3,4,5}; Ф = {{4,5},{3,4,5}}.
Далее проводится минимизация полученного множества Ф - устранение всех повторений множеств в текущем списке и удаление всех множеств, содержащихся в других множествах списка:
Ф = {{3,4,5}}.
Добавляем в список все пары, состоящие из ai и различных состояний из Аi и не являющиеся подмножествами других членов списка Ф (при i = 3 таких добавлений нет).
Приведём полностью результат применения второго шага ко всем столбцам:
Ф = {{4,5}};
{3}~{4,5}, Ф = {{3,4,5}};
{2}~{3}, Ф = {{3,4,5},{2,3}};
{1}~{2,4}, Ф = {{3,4,5},{2,3},{1,2},{1,4}};
В список Ф, полученный после второго шага, добавляются все одноэлементные множества, состоящие из состояний, не включенных ни в какие другие максимальные классы совместимости (в нашем примере таких нет).
Очевидно, что результирующий список Ф является списком всех максимальных классов совместимости. Таким образом, для автомата, рассмотренного нами, множество всех классов совместимости
Ф = {{3,4,5},{2,3},{1,2},{1,4}}.
Второй этап - нахождение минимального замкнутого покрытия - достаточно сложная задача, связана с перебором возможных замкнутых покрытий и здесь не рассматривается. Подробное описание алгоритма можно найти в книге С.И.Баранова "Синтез микропрограммных автоматов".
Мы же в качестве исходного замкнутого покрытия возьмем множе-ство максимальных классов совместимости Ф = {{1,2},{1,4},{2,3},{3,4,5}}.
Третий этап
Процедура получения автомата S' = (A', Z', W', ', '), представляе-мого найденным для исходного автомата S замкнутым покрытием D, достаточно проста. Каждому классу совместимости CiD ставится в соответствие состояние ai' нового автомата S'. Для каждого класса Ci D и каждого Zi Z вычисляется множество следующих за Ci состояний Ti=(Сi,Zi). Функции переходов определяются как
Применим эту процедуру к нашему примеру. В качестве исходного замкнутого покрытия, как уже отмечалось выше, возьмем множество максимальных классов совместимости Ф={{1,2},{1,4},{2,3},{3,4,5}} = {b1, b2, b3, b4}.
Классу совместимости {1,2} ставим в соответствие состояние b1 нового автомата.
За классом {1,2} по входу Z1 следует класс {2,3}, по входу Z2 - класс {5}, по Z3 - класс {2,3}, по Z4 - {2}. Следовательно, в автомате, получающим-ся в результате совмещения состояний {1,2}, должны быть совместимы состояния {1,2}, {2,3}, {5}, {2,3}, {2}, что в нашем случае верно.
Таким образом, получаем следующие значения функций переходов и выходов: '(b1, Z1) =b3, '(b1, Z2)=b4, '(b1, Z3)=b3, '(b1, Z4) = b1. '(b1, Z1) = w1, '(b1, Z2) = w2, '(b1, Z3) = w1, '(b1, Z4) = w1.
Аналогичную процедуру проводим для остальных классов совместимости. Получаем результат, приведённый в табл.1.14 и табл.1.15.
Таблица 1.15 |
||||
|
b1 |
b2 |
b3 |
b4 |
z1 |
w1 |
w1 |
w1 |
w1 |
z2 |
w2 |
w2 |
w2 |
w2 |
z3 |
w1 |
-- |
w1 |
w2 |
z4 |
w1 |
w1 |
w1 |
w1 |
Таблица 1.14 |
||||
|
b1 |
b2 |
b3 |
b4 |
z1 |
b3 |
b1 |
b3 |
b3 |
z2 |
b4 |
b1 |
b4 |
b2 |
z3 |
b3 |
b3 |
b1 |
b1 |
z4 |
b1 |
b1 |
b4 |
b4 |
Число минимальных замкнутых покрытий для некоторых частичных автоматов может значительно превышать число состояний этих автоматов. Поэтому практически более важной задачей является поиск одного минимального замкнутого покрытия для заданного автомата.
В частности, в нашем примере минимальным замкнутым покрыти-ем является {{1,2},{2,3},{4,5}}. Соответствующий этому покрытию мини-мальный автомат имеет всего три состояния (табл.1.16 и табл. 1.17).
Таблица 1.16 |
|
|
Таблица 1.17 |
||||||
|
{1,2} |
{2,3} |
{4,5} |
|
{1/2} |
{2,3} |
{4,5} |
||
z1 |
{2,3} |
{2,3} |
– |
z1 |
w1 |
w1 |
– |
||
z2 |
{4,5} |
{4,5} |
{1,2} |
z2 |
w2 |
w2 |
w2 |
||
z3 |
{2,3} |
{1,2} |
{1,2} |
z3 |
w1 |
w1 |
w2 |
||
z4 |
{1,2} |
{4,5} |
– |
z4 |
w1 |
w1 |
– |