- •Проектирование автоматов
- •Проектирование автоматов
- •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. Абстрактные автоматы
Определение. Абстрактным автоматом Мили называется преобразователь, представимый пятёркой
S=<Z, W, A, , >,
где Z – входной алфавит {z1, z2, …, zr},
W – выходной алфавит {w1, w2,…, wp},
A – алфавит состояний {a1, a2,…, at},
– функция переходов AxZ А,
– функция выходов AxZ W.
Если, кроме того, определено начальное состояние автомата a0 (a0 – символ из А), то говорят об инициальном автомате Мили.
Семантика: автомат функционирует в дискретном времени. В лю-бой момент времени он находится в некотором состоянии ai из множест-ва A, и на его вход поступает входной сигнал zi из множества Z. В зави-симости от состояния и входного сигнала в следующий момент автомат переходит в новое состояние aj, определяемое функцией перехода, aj=(ai, zi), при этом на его выходе формируется выходной сигнал w=(ai, zi) (рис.1.1). В инициальном автомате в начале функционирова-ния автомат находится в состоянии a0 .
А втомат Мили представляется матрицей переходов и матрицей выходов, описывающими соответствующие функции.
Пример 1. Автомат задан на множествах входов Z={z1, z2, z3}, состояний A={a1, a2, a3, a4, a5, a6} и выходов W={w1, w2}. Его функционирование описывается матрицами переходов и выходов, приведёнными в табл.1.1 и 1.2.
Таблица 1.1 |
|
Таблица 1.2 |
||||||||||||
|
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
|
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
|
z1 |
a3 |
a5 |
a6 |
a6 |
a1 |
a5 |
z1 |
w1 |
w1 |
w2 |
w1 |
w2 |
w1 |
|
z2 |
a1 |
a6 |
a4 |
a4 |
a4 |
a1 |
z2 |
w1 |
w1 |
w1 |
w1 |
w1 |
w1 |
|
z3 |
a5 |
a1 |
a3 |
a2 |
a5 |
a3 |
z3 |
w1 |
w1 |
w2 |
w2 |
w2 |
w1 |
Автомат Мили может быть также представлен в виде объединённой матрицы. В этом случае каждая клетка матрицы состоит из двух частей, в одной из которых записывается следующее состояние (функция (ai, z)), во второй части – выход (функция (ai, z)).
Таблица 1.3 |
||||||
|
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
z1 |
a3w1 |
a5w1 |
a6w2 |
a6w1 |
a1w2 |
a5w1 |
z2 |
a1w1 |
a6w1 |
a4w1 |
a4w1 |
a4w1 |
a1w1 |
z3 |
a5w1 |
a1w1 |
a3w2 |
a2w2 |
a5w2 |
a3w1 |
Автомат Мили может быть описан в виде графа. Вершинам этого графа сопоставлены состояния, дугам – переходы. При этом на каждой дуге записывается значение входа, определяющего этот переход, и значение выхода на этом переходе. Эта пара вход-выход называется весом дуги. Для рассмотренного автомата граф имеет вид как на рис.1.2
Рис.1.2
Автоматом Мура называют автомат, в котором функция выходов зависит только от состояния, то есть для него функция выходов автомата: : AW.
Пример 2. Автомат Мура задан на тех же множествах, что и автомат в примере 1, а его функционирование описывает табл. 1.4.
В графе автомата Мура дуги взвешиваются только значением соответствующего входа, значение выходов приписываются его вершинам.
Таблица 1.4 |
||||||
|
w a1 |
w1 a2 |
w2 a3 |
w1 a4 |
w2 a5 |
w1 a6 |
z1 |
a3 |
a5 |
a6 |
a6 |
a1 |
a5 |
z2 |
a1 |
a6 |
a4 |
a4 |
a4 |
a1 |
z3 |
a5 |
a1 |
a3 |
a2 |
a5 |
a3 |
Рис.1.3
Реакция автомата в состоянии ai на входное слово z* определяется по таблицам переходов и выходов. Для последнего примера реакцией автомата в состоянии a2 на слово z1z2z1 будет слово w2w1w1.