Самостоятельное изучение схемотехники. Абстрактный автомат. Часть 2
Статья написана, собрана и сверстана Brotherofken. Спасибо ему огромное.
В предыдущей статье я попытался изложить все основные определения и принципы, чтобы сделать эту статью максимально понятной. Все не уместилось, так что я настоятельно советую ознакомиться с этими файлами:
Базис, Базис2, Минимизация. Далее в этой статье я оставил несколько разъясняющих пометок курсивом.
В этой статье я попробую объяснить доступным языком что такое абстрактный автомат, способы его представления. Так как теория автоматов полна математики и сложна, постараюсь писать человеческим языком, чтобы неподготовленный читатель смог понять о чём идёт речь.
Электронные цифровые схемы формально можно разделить на 2 класса:
- Комбинационные Схемы (КС) – не обладают памятью. Выходной сигнал формируется в зависимости от комбинации входных данных в фиксированный момент времени (учитывая задержку на преобразования сигналов).Комбинационные схемы, их типы и принципы построения могут быть темой для отдельной статьи, а в качестве примеров можно привести: Управляемые шины, мультиплексоры и демультиплексоры, дешифраторы и шифраторы, преобразователи кодов, комбинационные счетчики и сумматоры и т. д.
- Схемы с памятью – алгоритм их работы зависит от состояния входов и памяти (того, что было в предыдущие моменты времени). Эти схемы описываются с применением теории конечных автоматов. Речь о них и пойдёт далее.
Другими словами первый класс — логические устройства, обрабатывающие входной сигнал. Второй элементы обладающие памятью и реагирующие на сигнал в зависимости от введенных в них данных.
Абстрактный автомат
Автомат должен будет реализовывать некоторые функции, которые заданы разработчиком. Он может быть простым сумматором, может реализовывать какую-либо микрокоманду процессора, выбирать слова из оперативной памяти или заниматься синтаксическим анализом выражения.
В общем виде, не вдаваясь в подробности, абстрактный автомат можно представить следующим образом: 
Или, если перейти от иллюстрации к математическому описанию:
A =
Такой автомат функционирует дискретно по времени, то есть значения входов, выходов и внутреннее состояние автомата изменяются в дискретные моменты времени.
Итак мы в общем виде описали что есть Абстрактный автомат. Примером такого автомата может быть триггер, регистр ЭВМ или сумматор.
Выделяют 2 типа автоматов:
- Автоматы Мили. Описывается системой уравнений:
c(t) = δ( a(t), c(t-1) );
b(t) = λ( a(t), c(t-1) ). - Автоматы Мура. Описывается уравнениями:
c(t) = δ( a(t), c(t-1) );
b(t) = λ( a(t), c(t) ).
Как видно состояние автомата c(t) в текущий момент времени является функцией его состояния в предыдущий момент времени и входного сигнала.
Отличаются автоматы видом функции выхода. В автомате Мили выходной сигнал определяется входным сигналом a(t) и состоянием автомата в предыдущий момент времени c(t-1). Выходной сигнал автомата Мура определяется парой входного сигнала a(t) и состояния в данный момент c(t).
Так же можно отметить, что от одного типа можно перейти ко второму и наоборот, причем при переходе от автомата Мили к автомату Мура число внутренних состояний автомата останется прежним, а при обратном переходе число внутренних состояний может возрасти. На этом останавливаться подробно не будем, считая, что синтезировали(нарисовали граф) автомат того типа, который надо.
Итак, на этом с матчастью окончено. Попробуем описать автоматы.
Т.е. автомат типа Мили вырабатывает выходной сигнал когда у него меняется входной, в зависимости от его предыдущего состояния. При этом длительность выходного сигнала не зависит от длительности входного, а только от его присутствия. В автоматах типа Мура выходной сигнал зависит от состояния автомата в текущий момент времени т.е. автомат будет вырабатывать определенный выходной сигнал пока не изменит свое состояние.
Способы задания автоматов
Как мы выяснили в первой части — автомат представляет собой совокупность входного и выходного алфавитов, множества внутренних состояний и функций, определяющих переходы и выходы. Однако, обычно функции δ и λ не заданы, и поведение автомата приходится описывать по-другому.
Есть два основных способа задания автомата:
- При помощи графов.
- При помощи таблиц переходов и выходов.
Графы
Граф автомата – это ориентированный связный граф, вершины которого символизируют внутренние состояния автомата, а дуги – переходы из одного состояния в другое.
Для графа Мили на дугах указываются сходные и выходные буквы. Выходные буквы пишутся над дугами, символизируя то, что выходное состояние зависит от состояния автомата в предыдущий момент времени.
Для графа автомата Мура на дугах записываются только входные буквы, выходные же указываются около вершин.
Важный момент: Если из каждой вершины выходит столько дуг, сколько есть входных букв, то автомат называется полным. Другими словами – если из каждой вершины определены переходы для каждой входной буквы. В наших примерах автомат Мили является полным, а автомат Мура – частичным.
И ещё: Если из одной вершины выходит дуг больше, чем входных букв (то есть 2 и более дуг с одинаковыми входными буквами), то такой автомат называется недетерминированным. Такое может произойти при построении формализованного описания и тогда надо будет произвести переход к детерминированному автомату, но это не всегда можно выполнить. Описание этого процесса я тоже упускаю, сразу нарисовав детерминированный автомат.
На этом о графах всё.
Таблицы переходов и выходов.
Графы нагляднее для человека, а таблицы — для машины. Любой автомат можно представить в виде таблицы переходов и выходов (ТПВ). В ТПВ строками являются внутренние состояния автомата, а столбцами – входные буквы.
Построим ТПВ для наших графов Мили и Мура. Если не определена какая-либо входная или выходная буква, то вместо неё ставится прочерк. Если не определено состояние, то действует это же простое правило.
ТПВ графа Мили
В ТПВ Мили в каждой клетке записаны переходы и выходы. Например, если автомат находится в состоянии С0 и на вход приходит буква a1, то он перейдёт в состояние С1 и на выходе появится буква b3.
ТПВ графа Мура
Для графа Мура строят отмеченную таблицу переходов. Выделяется дополнительный столбец для выходных букв.
В клетке под входной буквой пишется в какое состояние автомат переходит, в крайней правой клетке — какую выходную букву возвращает.
Пример синтеза автомата
При помощи абстрактных автоматов можно описать практически что угодно. Можно описать работу цифровой схемы, а можно – синтаксический или лексический анализатор. Попробуем описать триггер – чем не автомат?
Чтобы задать граф нужно словесное описание алгоритма работы триггера. Читаем:
Кодируем входной и выходной алфавиты:
A =
B =
Строим граф автомата Мили:
Вот такая забавная чебурашка получилась :-). Теперь можно построить таблицу переходов и выходов:
Если расписать эту таблицу преобразовав условные обозначения в фактические, то получим таблицу которая представляет из себя таблицу переходов триггера. Затем её можно упростить:
Нанесём полученную функцию на карту Вейча и минимизируем:
Выпишем, что получилось:
Строим по функции схему (Выполняли домашнее задание?):
Немного непривычно видеть триггер в булевом базисе, поэтому переведём функцию в базис И-НЕ и нарисуем схему в нём:
А на схеме асинхронный RS триггер обозначается вот так:
Теперь если приложить немного старания, то можно самостоятельно синтезировать простую новогоднюю гирлянду.
Источник
Способы задание абстрактного автомата
Наиболее распространены табличный и графический способы задания абстрактных автоматов.
Задание автомата Мили
1. Табличный способ.
Автомат Мили задается таблицей переходов и выходов.
Пусть автомат иметь состояние A =
Таблица переходов δ
| am zf | a1 | a2 | a3 |
| z1 | a2 | a3 | a3 |
| z2 | a3 | a2 | a1 |
Таблица выходов λ
| am zf | a1 | a2 | a3 |
| z1 | w2 | w1 | w2 |
| z2 | w2 | w1 | w1 |
Обе таблицы можно объединить в совмещенную таблицу переходов и выходов.
| am zf | a1 | a2 | a3 |
| z1 | a2 w2 | a3 w1 | a3 w2 |
| z2 | a3 w2 | a2 w1 | a1 w1 |
2. Графический способ
Основан на представлении абстрактного автомата в виде ориентированного графа, вершины которого соответствуют состояниям автомата, а дуги переходам между ними (рисунок 4).
Рисунок 4 – Представление абстрактного автомата в виде графа
Тогда автомат Мили согласно совмещенной таблице переходов и выходов имеет следующий вид.
Задание автомата Мура
1. Табличный способ
Составляется отмеченная таблица переходов и выходов.
| wg | w1 | w2 | w1 | w1 |
| am zf | a1 | a2 | a3 | a4 |
| z1 | a2 | a3 | a4 | a4 |
| z2 | a4 | a1 | a1 | a1 |
2. Графический способ
Автомат Мура согласно отмеченной таблице имеет следующий вид.
Источник
Матричный способ задания автоматов
Матричный способ является наиболее общим способом описания автомата. Матрица соединения автомата – квадратная матрица Сij=||cij||, строки которой соответствуют исходным состояниям системы, а столбцы — состояниям переходов. Элемент матрицы cij=xk/ys, где xk – входной сигнал, вызывающий переход zi — > zj, ys – значение выходного сигнала, выдаваемое на этом переходе. Для автомата Мура элемент cij равен множеству входных сигналов при переходе zi — > zj, а выход описывается вектором, i-я компонента которого – это выходной сигнал. C=||Cij||, строки – исходные состояния, столбцы – состояния перехода.
Элемент Cij=xk/ys, стоящий на пересечении i-й строки и j-го столбца (автомат Мили) – входной сигнал xk, вызывающий переход из состояния zi ® zj и выходной сигнал ys.
Для автомата Мили матрица соединений:
(8)
Если zi ® zj происходит под действием нескольких воздействий, то элемент матрицы Cij – множество пар «вход – выход» для этого перехода, соединенных знаком дизъюнкции.
Для F–аппарата Мура Cij – множество входных воздействий при переходе (zi, zj), а выход описывается вектором выходов
|
, (9)
Для детерминированных автоматов выполняется условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного воздействия не может перейти более чем в одно состояние, то есть для графического задания: в графе автомата из любой вершины не могут выходить два и более ребра, отмеченные одним и тем же входным сигналом. Аналогично в матрице соединений в каждой строке любое входное воздействие не должно встречаться более одного раза.
Рассмотрим таблицу переходов и граф асинхронного конечного автомата. Для F-автомата состояние zR – устойчивое, если для любого входа xi Î X, для которого j (zR, xi)=zR, имеет место Y (zR, xi)=yR. Т.о., F-автомат называется асинхронным, если каждое его состояние zR Î Z устойчиво.
На практике автомат всегда является асинхронным, а устойчивость его обеспечивается, например, введением сигналов синхронизации.
Источник
