26 апреля 2010 в 19:06

Самостоятельное изучение схемотехники. Абстрактный автомат. Часть 2

• Электроника для начинающих

Статья написана, собрана и сверстана . Спасибо ему огромное.
В предыдущей статье я попытался изложить все основные определения и принципы, чтобы сделать эту статью максимально понятной. Все не уместилось, так что я настоятельно советую ознакомиться с этими файлами:
Базис , Базис2 , Минимизация . Далее в этой статье я оставил несколько разъясняющих пометок курсивом.

В этой статье я попробую объяснить доступным языком что такое абстрактный автомат, способы его представления. Так как теория автоматов полна математики и сложна, постараюсь писать человеческим языком, чтобы неподготовленный читатель смог понять о чём идёт речь.

Электронные цифровые схемы формально можно разделить на 2 класса:

• Комбинационные Схемы (КС) – не обладают памятью. Выходной сигнал формируется в зависимости от комбинации входных данных в фиксированный момент времени (учитывая задержку на преобразования сигналов).Комбинационные схемы, их типы и принципы построения могут быть темой для отдельной статьи, а в качестве примеров можно привести: Управляемые шины, мультиплексоры и демультиплексоры, дешифраторы и шифраторы, преобразователи кодов, комбинационные счетчики и сумматоры и т. д.
• Схемы с памятью – алгоритм их работы зависит от состояния входов и памяти (того, что было в предыдущие моменты времени). Эти схемы описываются с применением теории конечных автоматов. Речь о них и пойдёт далее.

Другими словами первый класс - логические устройства, обрабатывающие входной сигнал. Второй элементы обладающие памятью и реагирующие на сигнал в зависимости от введенных в них данных.

Абстрактный автомат

Автомат должен будет реализовывать некоторые функции, которые заданы разработчиком. Он может быть простым сумматором, может реализовывать какую-либо микрокоманду процессора, выбирать слова из оперативной памяти или заниматься синтаксическим анализом выражения.
В общем виде, не вдаваясь в подробности, абстрактный автомат можно представить следующим образом:

Или, если перейти от иллюстрации к математическому описанию:
A =

Обозначения:

1. Множество {A} – представляет собой множество значений на физических входах автомата. На входе в нашем случае будет какая-то последовательность высоких и низких уровней напряжения, которые будут кодировать логические нули и единицы.
2. Множество {B} – представляет собой множество значений на физических выходах автомата.
3. Множество {C} – а множество, которое представляет внутреннее состояние автомата – память. На будущее C0 будем обозначать начальное состояние автомата.
4. δ = X × Z → Z – это функции переходов автомата, они однозначно определяют состояние ai в которое переходит автомат из состояния aj.
5. λ = X × Z → Y – функции выходов, они определяют что находится на выходе автомата в зависимости от входов и внутреннего состояния.

δ и λ не показаны на схеме для визуального упрощения.

Такой автомат функционирует дискретно по времени, то есть значения входов, выходов и внутреннее состояние автомата изменяются в дискретные моменты времени.
Итак мы в общем виде описали что есть Абстрактный автомат. Примером такого автомата может быть триггер, регистр ЭВМ или сумматор.

Выделяют 2 типа автоматов:

1. Автоматы Мили. Описывается системой уравнений:
   c(t) = δ(a(t), c(t-1));
   b(t) = λ(a(t), c(t-1)).
2. Автоматы Мура. Описывается уравнениями:
   c(t) = δ(a(t), c(t-1));
   b(t) = λ(a(t), c(t)).

Как видно состояние автомата c(t) в текущий момент времени является функцией его состояния в предыдущий момент времени и входного сигнала .
Отличаются автоматы видом функции выхода. В автомате Мили выходной сигнал определяется входным сигналом a(t) и состоянием автомата в предыдущий момент времени c(t-1). Выходной сигнал автомата Мура определяется парой входного сигнала a(t) и состояния в данный момент c(t).
Так же можно отметить, что от одного типа можно перейти ко второму и наоборот, причем при переходе от автомата Мили к автомату Мура число внутренних состояний автомата останется прежним, а при обратном переходе число внутренних состояний может возрасти. На этом останавливаться подробно не будем, считая, что синтезировали(нарисовали граф) автомат того типа, который надо.
Итак, на этом с матчастью окончено. Попробуем описать автоматы.

Т.е. автомат типа Мили вырабатывает выходной сигнал когда у него меняется входной, в зависимости от его предыдущего состояния. При этом длительность выходного сигнала не зависит от длительности входного, а только от его присутствия. В автоматах типа Мура выходной сигнал зависит от состояния автомата в текущий момент времени т.е. автомат будет вырабатывать определенный выходной сигнал пока не изменит свое состояние.

Способы задания автоматов

Как мы выяснили в первой части - автомат представляет собой совокупность входного и выходного алфавитов, множества внутренних состояний и функций, определяющих переходы и выходы. Однако, обычно функции δ и λ не заданы, и поведение автомата приходится описывать по-другому.

Есть два основных способа задания автомата:

1. При помощи графов.
2. При помощи таблиц переходов и выходов.

Графы

Граф автомата – это ориентированный связный граф, вершины которого символизируют внутренние состояния автомата, а дуги – переходы из одного состояния в другое.

Для графа Мили на дугах указываются сходные и выходные буквы. Выходные буквы пишутся над дугами, символизируя то, что выходное состояние зависит от состояния автомата в предыдущий момент времени.

Для графа автомата Мура на дугах записываются только входные буквы, выходные же указываются около вершин.

Важный момент: Если из каждой вершины выходит столько дуг, сколько есть входных букв, то автомат называется полным . Другими словами – если из каждой вершины определены переходы для каждой входной буквы. В наших примерах автомат Мили является полным , а автомат Мура – частичным .
И ещё: Если из одной вершины выходит дуг больше, чем входных букв (то есть 2 и более дуг с одинаковыми входными буквами), то такой автомат называется недетерминированным . Такое может произойти при построении формализованного описания и тогда надо будет произвести переход к детерминированному автомату, но это не всегда можно выполнить. Описание этого процесса я тоже упускаю, сразу нарисовав детерминированный автомат.
На этом о графах всё.

Таблицы переходов и выходов.

Графы нагляднее для человека, а таблицы - для машины. Любой автомат можно представить в виде таблицы переходов и выходов (ТПВ). В ТПВ строками являются внутренние состояния автомата, а столбцами – входные буквы.
Построим ТПВ для наших графов Мили и Мура. Если не определена какая-либо входная или выходная буква, то вместо неё ставится прочерк. Если не определено состояние, то действует это же простое правило.

ТПВ графа Мили

В ТПВ Мили в каждой клетке записаны переходы и выходы. Например, если автомат находится в состоянии С0 и на вход приходит буква a1, то он перейдёт в состояние С1 и на выходе появится буква b3.

ТПВ графа Мура

Для графа Мура строят отмеченную таблицу переходов. Выделяется дополнительный столбец для выходных букв.
В клетке под входной буквой пишется в какое состояние автомат переходит, в крайней правой клетке - какую выходную букву возвращает.

Пример синтеза автомата

При помощи абстрактных автоматов можно описать практически что угодно. Можно описать работу цифровой схемы, а можно – синтаксический или лексический анализатор. Попробуем описать триггер – чем не автомат?
Чтобы задать граф нужно словесное описание алгоритма работы триггера. Читаем:

Кодируем входной и выходной алфавиты:
A = {a0, a1}, где a0 – логическая 1 на входе R, a1 – логическая единица на входе S.
B = {b0, b1}, где b0 – логический 0 на выходе Q, b1 – логическая единица на выходе Q.
Строим граф автомата Мили:


Вот такая забавная чебурашка получилась:-). Теперь можно построить таблицу переходов и выходов:

Если расписать эту таблицу преобразовав условные обозначения в фактические, то получим таблицу которая представляет из себя таблицу переходов триггера. Затем её можно упростить:

Нанесём полученную функцию на карту Вейча и минимизируем:

Выпишем, что получилось:

Строим по функции схему (Выполняли домашнее задание?).

Цифровом (дискретный) автомат можно трактовать как устройство, осуществляющее прием, храпение и преобразование дискретной информации по некоторому алгоритму. С определенной точки зрения к автоматам можно отнести как реальные устройства (вычислительные машины, живые организмы и т. п.), так и абстрактные системы (математические машины, аксиоматические теории

Общую теорию автоматов подразделяют на абстрактную и структурную. Различие между ними заключается в том, что абстрактная теория, отвлекаясь от структуры автомата (т. е. не интересуясь способом его построения), изучает лишь поведение автомата относительно внешней среды. Абстрактная теория автоматов близка, таким образом, теории алгоритмов, являясь по существу ее дальнейшей детализацией. В противоположность абстрактной теории, структурная интересуется как структурой самого автомата, так и структурой входных воздействий и реакций автомата на них. В структурной теории изучаются способы построения автоматов, способы кодирования входных воздействий и реакций автомата. Таким образом, структурная теория автоматов является продолжением и дальнейшим развитием абстрактной теории. Опираясь на аппарат булевых функций и на абстрактную теорию автоматов, структурная теория дает эффективные рекомендации по разработке реальных устройств вычислительной техники.

Абстрактный цифровой автомат А определяется совокупностью пяти объектов где - множество входных сигналов автомата А (входной алфавит автомата А); - множество состояний автомата А (алфавит состояний автомата - множество выходных сигналов автомата А (выходной алфавит автомата А); - функция переходов

автомата А, задающая отображение т. е. ставящая в соответствие любой паре элементов декартового произведения множеств элемент множества - функция выходов автомата А, задающая либо отображение либо отображение

Иныш словами, функция переходов показывает, что автомат А, находясь в некотором состоянии при появлении входного сигнала , переходит в некоторое состояние Последнее может быть записано также и выражением Функция выходов задающая отображение показывает, что автомат Л, находясь в некотором состоянии при появлении входного сигнала , выдает выходной сигнал Последнее может быть записано выражением

По способу формирования функции выходов выделяют три типа абстрактных автоматов: автомат Мили, автомат Мура, С-автомат. В абстрактном автомате Мили функция выходов X задает отображение . В абстрактном автомате Мура функция выходов задает отображение абстрактном С-автомате вводятся две функции выходов X, и задающие отображение соответственно. При этом алфавит выходов С-автомата либо

Произвольный абстрактный автомат Милан или Мура имеет один входной и один выходной каналы (рис. 10.1). Произвольный абстрактный С-автомат имеет один входной и два выходных канала (рис. 10.2).

Выделяют полностью определенные и частичные автоматы.

Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов и функция выходов определены для всех пар

Частичным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар

Абстрактный цифровой автомат называется инициальным, если на множестве его состояний 5 выделяется специальное начальное со стояние т. е. инициальный абстрактный автомат определяется совокупностью шести объектов Выделение на множестве начального состояния объясняется чисто практическими соображениями, связанными с возникающей часто необходимостью фиксировать условия начала работы автомата.

Говорят, что абстрактный автомат функционирует в дискретном автоматном времени , и переходы из состояния в состояние осуществляются мгновенно. В каждой момент дискретного времени автомат находится в некотором состоянии из множества состояний Если автомат инициальный, то в начальный момент времени он всегда находится в начальном состоянии . В момент находясь в состоянии автомат способен воспринять на входе букву входного алфавита соответствии с функцией выходов X он выдаст в тот же момент времени букву выходного алфавита и в соответствии с функцией переходов перейдет в следующее

состояние Согласно определению абстрактного автомата, автомат Мили в этом случае характеризуется системой уравнений:

автомат Мура - системой уравнений;

а С-автомат - системой уравнений:

Иными словами, если на вход инициального абстрактного автомата Мили или Мура, установленного в начальное состояние подавать буква за буквой некоторую последовательность букв входного алфавита входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита выходное слово. Для случая С-автомата на его выходах будут появляться две ледовательности: абстрактном С-автомате выходной сигнал выдается все премии пока лнтомит находится в состоянии Выходной сигнал им лаетея во время действия входного сигнала при нахождении С-автомата и состоянии

Таким образом, на уровне абстрактной теории функционирование цифрового автомата понимается как преобразование входных слов в выходные слова.

Понятие состояния в определении абстрактного автомата введено в связи с тем, что большинство реальных процессов, которыми управляют реально построенные цифровые автоматы, требуют для своего правильного течения знания предыстории развития процесса во времени. Иными словами, выходной сигнал, выдаваемый автоматом в данный момент времени, определяется не только входным воздействием на автомат, но и состоянием, в котором автомат в этот момент времени находился Например, если нужно построить автомат управления переключением светофора при условии, что на вход автомата поступает только сигнал «переключить светофор», то в каждый момент времени для организации правильной работы автомата, кроме входного сигнала «переключить светофор», необходимо иметь информацию о положении светофора в предшествующий момент времени. Эта информация и обеспечивается наличием различных состояний абстрактного автомата. Абстрактные цифровые автоматы, соответствующие введенному определению абстрактного автомата, называют также абстрактными автоматами с памятью, так как существование в автомате множества различных его состояний возможно только при наличии у автомата памяти.

Ряд процессов, которыми управляют реальные автоматы, не требуют для своего правильного течения знания предустории развития процесса во времени. В автоматах, управляющих такими процессами,

Таблица 10.1

выходной сигнал определяется только входным воздействием на автомат. У казанные автоматы на абстрактном уровне представления определяются с помощью тройки , где функция выходов задает отображение и называются абстрактными автоматами с тривиальной памятью либо комбинационными автоматами. Простейшим аналогом комбинационного автомата можно ечитать обыкновенный электрический фонарь при условии, что входным воздействием является нажатие кнопки «Вкл», а выходным сигналом - зажигание лампочки фонаря.

Алфавиты входов, состояний и выходов автоматов задаются, как обычные множества, например, перечислением своих элементов. Функции переходов и выходов могут быть заданы матрично, графически и аналитически. Поэтому любой абстрактный автомат может быть задан тремя способами! матрично, графически и аналитически

При матричном способе автомат представляется либо двумя таблицами: таблицей переходов и таблицей выходов, либо матрицей соединений Таблица переходов задает отображение т. е. определяет функцию переходов автомата Таблица выходов, в зависимости от типа рассматриваемого автомата, задает либо отображение либо , т. е. определяет функцию выходов автомата.

Таблица переходов произвольного полностью определенного абстрактного автомата строится следующим образом. Столбцы таблицы помечаются буквами входного алфавита автомата, а строки таблицы - буквами алфавита состояний автомата. В клетке таблицы переходов, находящейся на пересечении столбца, отмеченного входным сигналом и строки, отмеченной состоянием ставится состояние являющееся результатом перехода автомата из состоянии под воздействием входного сигнала что определяется выражением Пример, таблицы переходов некоторого абстрактного полностью определенного автомата с входным алфавитом и алфавитом состояний представлен в табл. 10.1. Если абстрактный автомат частичный, то в клетке таблицы его переходов, находящейся на пересечении столбца, отмеченного входным сигналом и строки, отмеченной состоянием (при условии, что переход из состояния под воздействием входного сигнала неопределен), ставится прочерк, и любое входное слово, приводящее к указанному переходу, является запрещенным. Заполнение остальных клеток аналогично случаю полностью определенного автомата. Пример таблицы переходов некоторого абстрактного частичного автомата с входным алфавитом и алфавитом состояний представлен в табл. 10.2. Вид таблицы переходов не зависит от типа задаваемого автомата (автомат Мура, Мили, С-автомат). Таблицы выходов автомата Мура, Мили, С-автомата имеют различия. Таблица выходов полностью определенного автомата Мили строятся следующим образом. Идентификация столбцов и строк, а также формат таблицы соответствует таблице переходов полностью определенного автомата. В клетке таблицы выходов,

Таблица 10.2

Таблица 10.3

Таблица 10.4

находящейся на пересечении столбца, отмеченного входным сигналом и строки, отмеченной состоянием ставится выходной сигнал который автомат Мили выдает, находясь в состоянии при наличии входного сигнала что определяется выражением Пример таблицы выходов некоторого абстрактного полностью определенного автомата Мили с входным алфавитом алфавитом состояний и выходным алфавитом представлен в табл. 10.3.

Таблица выходов полностью определенного автомата Мура строится более просто: каждому состоянию автомата приписывается свой выходной сигнал. Пример таблицы выходов автомата Мура с алфавитом состояний и выходным алфавитом представлен в табл 10.4.

Очевидно, абстрактный полностью определенный С-автомат задается двумя таблицами выходов, первая из которых ечть таблица выходов автомата Мили, а вторая - таблица выходов автомата Мура.

Если автомат Мили частичный, то в некоторых клетках его таблицы выходов может стоять прочерк, означающий отсутствие выходного сигнала. При этом прочерк обязательно ставится в тех клетках таблицы выходов, которые соответствуют таким же клеткам с прочерком в таблице переходов автомата Мили. Последнее связано с тем, что если в частичном автомате Мили имеется пара ) и такая, что переход из состояния под воздействием входного сигнала неопределеи, то, естественно, неопределено и значение выходного сигнала на таком (несуществующем) переходе. Пример таблицы выходов частичного автомата Мили, заданного таблицей переходов (табл. 10.2) с выходным алфавитом представлен в табл. 10.5

Прочерки в некоторых клетках таблицы выходов частичного автомата Мура не связаны с прочерками в клетках его таблицы переходов. Это определяется тем, что выходной сигнал автомата Мура зависит только от состояния, в котором находится автомат. Например, таблица выходов частичного автомата Мура, заданного таблицей переходов (табл. 10.2),

Таблица 10.5

Таблица 10.6.

Таблица 10.7

может быть представлена и как табл. 10.4, если в каждом своем состоянии автомат выдает какой-то выходной сигнал, и как табл. 10.6, если значение выходного сигнала автомата для некоторых состояний неоиределено.

На практике таблицы переходов и выходов автомата часто совмещаются в одну таблицу, называемую отмеченной таблицей переходов автомата. Отмеченная таблица переходов полностью определенного автомата Мили, представленного таблицей переходов (табл. 10.1) и таблицей выходов (табл. 10.3), сведена в табл. 10.7. Отмеченная таблица переходов частичного автомата Мура (табл. 10.2) и таблица выходов (табл. 10.4), сведена в табл. 10.8.

Кроме рассмотренных выше таблиц переходов и выходов, произвольный абстрактный автомат может быть описан матрицей соединений. Такое описание - один из способов матричного задания абстрактных автоматов. Матрица соединений произвольного абстрактного автомата является квадратной и содержит столько столбцов (строк), сколько различных состояний имеет рассматриваемый автомат. Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата. Если автомат инициальный, то первый слева столбец и первая сверху строка матрицы его соединений помечаются буквой начального состояния автомата В клетке матрицы соединений, находящейся на пересечении столбца, помеченного буквой состояния и строки, помеченной буквой состояния автомата, ставится входной сигнал (или дизъюнкция входных сигналов), под воздействием которого осуществляется переход автомата из состояния в состояние Если матрицей соединения задается абстрактный автомат Милн, то рядом с буквой входного сигнала в скобках указывается буква выходного сигнала который автомат Мили выдает, осуществляя переход Матрица соединений некоторого автомата Мили, представленного отмеченной таблицей переходов (табл. 10.7), показана на рис. 10.3.

Если матрицей соединения задается абстрактный автомат Мура, то выходными сигналами помечаются состояния автомата, идентифицирующие строки матрицы соединений.

Таблица 10.8

При графическом способе задания абстрактные автоматы представляются ориентированными графами; состояния автомата изображаются вершинами графа, а переходы между состояниями - дугами между соответствующими вершинами. При этом каждой дуге графа приписывается некоторая буква входного алфавита автомата, указывающая, что данный переход автомата осуществляется только при появлении входного сигнала и каждой вершине графа - буква соответствующего состояния автомата. Если графом изображается автомат Мила, то выходные сигналы автомата проставляются на дугах графа (в соответствии с таблицей выходов автомата) рядом с буквой входного сигнала. Пример графа автомата Мили, заданного таблицей переходов (табл. 10.1) и таблицей выходов (табл. 10.3), показан на рис. 10.4. Если графом изображается автомат Мура, то выходные сигналы автомата проставляются около вершин графа (в соответствии с таблицей выходов автомата). Пример графа автомата Мура, заданного таблицей переходов (табл. 10.2) и таблицей выходов (табл. 10.4), показан на рис. 10.5.

При аналитическом способе задания абстрактные автоматы представляются четверкой объектов где задает для каждого состояния автомата отображение . Другими словами, при аналитическом способе задания для каждого состояния автомата указывается отображение представляющее собой множество всех троек и таких, что под воздействием входного сигнала автомат осуществляет переход из состояния в состояние выдавая при этом выходной сигнал Применительно к общему определению абстрактного автомата, последнее равнозначно описанию функций и X в соответствии с выражениями: Отображение записывается следующим образом:

Аналитическое задание автомата Мили, представленного отмеченной таблицей переходов (табл. 10.7), имеет следующий вид.

Рассмотрим эквивалентное преобразование автоматов. Эквивалентными называются автоматы, индуцирующие одно и то же отображение множества слов во входном алфавите в множество слов в выходном алфавите. Рассмотрим только преобразование автомата Мура в эквивалентный ему автомат Мили. Преобразование автомата Мили в эквивалентный ему автомат Мура осуществляется несколько сложнее.

Переход от автомата Мура к эквивалентному ему автомату Мили удобно осуществлять при графическом способе задания автоматов. В этом случае он сводится к переносу выходного сигнала выдаваемого автоматом Мура в состоянии на дуги, входящие в вершину, помеченную буквой При матричном способе задания таблица переходов автомата Мили совпадает с таблицей переходов автомата Мура, а таблица выходов автомата Мили получается из его таблицы переходов заменой буквы состояния находящейся на пересечении столбца, отмеченного входным сигналом и строки на выходной сигнал выдаваемый автоматом Мура в состоянии

Разработка реальных автоматов (представленных хотя бы на уровне принципиальных электрических схем) требует их задания сначала на абстрактном уровне с последующим переходом на структурный уровень, учитывающий используемые в схеме автомата логические элементы и связи между ними. В связи с этим возникает задача синтеза абстрактного автомата, исходя из какого-то начального, например, словесного описания его работы. Существующие алгоритмы синтеза абстрактных автоматов на практике обычно не используются из-за сложности и громоздкости вычислеиий и поэтому не включены в материал учебника. Однако для лучшего уяснения понятия абстрактного автомата и способов его задания здесь рассмотрим пример синтеза абстрактного автомата, основываясь на чисто умозрительных соображениях.

Пример. Построить абстрактный цифровой автомат управления переключением спетофора при условии, что на вход автомата поступает только сигнал «переключить светофор». Обозначим этот сигнал буквой а его отсутствие - буквой

Очевидно, входной алфавит X такого автомата будет состоять из двух букв: Так как синтезируемый автомат должен обеспечивать переключение светофора в красный, желтый и зеленый цвет, то введем три соответствующих выходных сигнала управления Положим также, что в момент начала функционирования автомат находится в состоянии Алгоритм работы тривиален; возможное решение для автомата Мили показано на рис. 10.6, а для автомата Мура - на рис. 10.7. Для (упрощения полагаем, что в начальный момент времени автомат Мура выдает выходной сигнал «включить зеленый цвет». Отметим, что для построения графа автомата потребуется ввести четыре различных состояния. Число состояний можно уменьшить, например увеличив число входных сигналов автомата либо расширив возможности автомата в плане запоминания предыстории развития процесса управления во времени (в рассматриваемом примере запоминается только момент выдачи последнего выходного сигнала).

В заключение отметим, что мы рассматриваем только детерминированные автоматы, у которых выполнено условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Автомат, заданный таблицей переходов, всегда детерминированный, так как на пересечении столбца и строки таблицы переходов записывается только одно состояние если переход определен, и ставится прочерк, если переход не определен. Применительно к графическому способу задания автомата условие однозначности означает, что в графе автомата из любой вершины не может выходить две и более дуги, отмеченные одним и тем же входным сигналом.

6 Основные понятия и определения теории абстрактных авто­матов (лекция №9)
Цифровой (дискретный) автомат (ЦА) – устройство, которое осуществляет прием, хранение и/или преобразование дискретной информации по некоторому алгоритму. Примерами ЦА могут служить живые организмы, процессоры, бытовая техника калькуляторы – это реальные устройства, а также есть абстрактные, например, модели алгоритмов. ЦА относятся к последовательным устройствам. Этот класс устройств определяется тем , что значение выходов зависит не только от входных значений, но и от текущего состояния устройства. Т.е. вводится понятие – состояние . Для того чтобы хранить данные о состоянии, в котором находится устройство в ЦА используются запоминающие элементы – триггеры.
6.1 Математическая модель цифрового автомата
Цифровой автомат - устройство, характеризующееся набором внутренних состояний в которое оно попадет под воз­действием команд заложенной в него программы. Переход автомата из одного состояния в другое осуществляется в определенный момент времени.

Математической моделью ЦА (а в общем случае любого дискретного устройства) является так называемый абстракт­ный автомат, определенный как 6-компонентный кортеж: S=(A,X,Y,,,а 1) у которого:

1. 
   A={a 1 , a 2 , ... ,a m } – алфавит состояний – множество состояний, в которых может находиться проектируемый цифровой автомат. Количество состояний играет важную роль при реализации ЦА. Чем больше состояний, тем больше требуется запоминающих элементов(триггеров) для построения ЦА.
2. 
   X={x 1 , x 2 , ... ,x f } – алфавит входных значений – множество значений, которые могут поступать на вход ЦА. Например , если у автомата двухразрядный двоичный вход, то элементами алфавита могут быть 00, 01, 10 и 11.
3. 
   Y={y 1 , y 2 , ..., y g } – алфавит выходных значений – множество значений, которые могут быть установлены на выходе ЦА.
4. 
   : AXA – функция переходов a(t+1)=  (x(t),a(t)) . Функция переходов определяет, в какое состояние a(t+1) перейдет автомат под воздействием входного сигнала x(t) , если в текущий момент времени автомат находится в состоянии a(t).
5. 
    : AZW – функция выходов y (t )=  (a (t ), x (t )). Функция выходов определяет какое выходное значение y (t ) будет установлено на выходе автомата в зависимости от входного значения x (t ) и текущего состояния a (t ) .
6. 
   a i  A - начальное состояние автомата –состояние в которое устанавливается ЦА после подачи питания или после сброса

Под алфавитом здесь понимается непустое множество попарно различных символов. Элементы алфавита называются буквами , а конечная упорядоченная последовательность букв - словом в данном алфавите.

Рисунок 6.1 – Абстрактный автомат

Абстрактный автомат (рисунок 6.1) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата , причем в начальный момент t = 0 он всегда находится в начальном со­стоянии a(0)=a1. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита X(t)  Z. В соответствии с функцией выходов он выдаст в тот же момент времени t букву выходного алфавита y(t)=(a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1)=, a(t)  A, y(t)  Y.

Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов вход­ного алфавита X во множество слов выходного алфавита Y. Т.е. если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита x(0), x(1),... - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита y(0), y(1),... - выходное слово. Т.о. выходное слово = (входное слово), где  - отображение, осуществляемое абстрактным автоматом.

На уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные. Можно сказать, что в абстрактном автомате отвлекаемся от его структуры - содержимого прямоугольника (рисунок 6.1), рассматривая его как "черный ящик", т.е. основное внимание уделяем поведению автомата относительно внешней среды.

Понятие состояния в определении автомата введено в связи с тем, что часто возникает необходимость в описании пове­дения систем, выходы которых зависят не только от состояния входов в данный момент времени, но и от некоторой пре­дыстории, т.е. от сигналов , которые поступали на входы системы ранее. Состояния как раз и соответствуют некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходной сигнал как функцию со­стояния и входа в данный момент времени.

6.2 Классификация цифровых автоматов

Рассмотренные выше абстрактные автоматы можно разделить на:

1. 
   полностью определенные и частичные;
2. 
   детерминированные и вероятностные;
3. 
   синхронные и асинхронные;

Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов и функция выходов определены для всех пар (a i , z j).

Частичным называется абстрактный автомат, у которого функция переходов или функция выходов , или обе эти функ­ции определены не для всех пар (a i , z j).

К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов: автомат, находя­щийся в некотором состоянии a i , под действием любого входного сигнала z j не может перейти более, чем в одно состоя­ние.

В противном случае это будет вероятностный автомат , в котором при заданном состоянии a i и заданном входном сиг­нале z j возможен переход с заданной вероятностью в различные состояния.

Для определения синхронных и асинхронных автоматов вводится понятие устойчивого состояния . Состояние a s автомата называется устойчивым, если для любого состояния a i и входного сигнала z j таких, что (a i , z j) = a s имеет место (a s , z j) = a s , т.е. состояние устойчиво, если попав в это состояние под действием некоторого сиг­нала zj, автомат выйдет из него только под действием другого сигнала z k , отличного от z j .

Автомат, у которого все состояния устойчивы - асинхронный .

Автомат называется синхронным , если он не является асинхронным.

Абстрактный автомат называется конечным , если конечны множества А = {a 1 , a 2 , ..., a m }, Z = {z 1 , z 2 , ..., z f }, W = {w 1 , w 2 , ..., w g }. Автомат носит название инициального , если в нем выделено начальное состояние a 1 .
6.3 Разновидности цифровых автоматов
На практике наибольшее распространение получили два класса автоматов - автоматы Мили (Mealy) и Мура (Moore).

Закон функционирования автомата Мили задается уравнениями:

a(t+1) = (a(t), z(t)); w(t) = (a(t), z(t)), t = 0,1,2,...
Закон функционирования автомата Мура задается уравнениями:
a(t+1)=(a(t), z(t)); w(t) = (a(t)), t = 0,1,2,...
Из сравнения законов функционирования видно, что, в отличие от автомата Мили, выходной сигнал в автомате Мура зависит только от текущего состояния автомата и в явном виде не зависит от входного сигнала. Для полного задания автомата Мили или Мура дополнительно к законам функционирования , необходимо указать начальное состояние и оп­ределить внутренний, входной и выходной алфавиты.

Кроме автоматов Мили и Мура иногда оказывается удобным пользоваться совмещенной моделью автомата, так на­зываемым С- автоматом.

Абстрактный С- автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита X, и двумя выходами, на которых появляются сигналы из алфавитов Y и U. Отличие С - автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов  1 и  2 , каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими уравнениями:
а(t+1) =(a(t), z(t)); w(t) = 1 (a(t), z(t)); u(t) =  2 (a(t)); t = 0, 1, 2, ...
Выходной сигнал U h = 2 (a m) выдается все время, пока автомат находится в состоянии a m . Выходной сигнал Wg= 1 (a m , z f) выдается во время действия входного сигнала Z f при нахождении автомата в состоянии a m .
7 Способы описания и задания автоматов (лекция№10)
Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, X, Y, , , а 1). Множества А, X, Y описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций  и  (следовательно и всего автомата в целом) наибольшее распространение получили табличный и графиче­ский.
7.1 Табличный способ описания цифровых автоматов

При табличном способе описания цифровых автоматов применяется два вида таблиц – таблица переходов и таблица выходов.

Таблица переходов отображает функцию переходов. Строкам таблицы соответствуют состояния автомата, т.е. в таблице столько строк, сколько состояний у автомата. Столбцам таблицы соответствуют входные значения , которые могут поступать на входы ЦА, т.е. столбцом столько – сколько элементов во входном алфавите. На пересечении i-столбца и j-строки в ячейке таблицы указывается состояние в которое перейдет ЦА под воздействием входного сигнала x i (которому соответствует i-й столбец) из состояния a j (которому соответствует j-я строка). Таблица переходов приведена на рисунке 6.2

	x 1	x 2	…	x m
a 1	a 2	a 1	…	a 2
a 2	a n-1	a 3	…	a 1
…			…
a n	-	a n	…	a 2

Рисунок 6.2 – Таблица переходов ЦА
Таблица переходов имеет одинаковый вид как для автомата Мура, так и для автомата Мили. Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте не определенных состояний и выходных сигналов ставится прочерк. В таких автоматах выходной сигнал на каком-либо переходе всегда не определен, если неопределенным является состояние перехода
Таблица выходов для автомата Мили имеет такой же вид как и таблица переходов , только на пересечении i-столбца и j-строки в ячейке таблицы указывается выходное значение, которое сформирует ЦА под воздействием входного сигнала x i (которому соответствует i-й столбец) в состоянии a j (которому соответствует j-я строка). Таблица выходов автомата Мили приведена на рисунке 6.3

	x 1	x 2	…	x m
a 1	y 1	y 3	…	y 1
a 2	y n-1	y 2	…	y n-1
…			…
a n	-	y 1	…	y 2

Рисунок 6.3 – Таблица выходов автомата Мили

Таблица выходов для автомата Мура состоит из одного столбца. Строкам таблицы соответствуют состояния автомата, т.е. в таблице столько строк, сколько состояний у автомата. Пример таблицы приведен на рисунке 6.4

	x 1
a 1	y 1
a 2	y n-1
…
a n	y 2

Рисунок 6.4 – Таблица выходов автомата Мура
В некоторых случаях вместо двух таблиц определяющих ЦА удобно применять совмещенную таблицу переходов и выходов. На рисунке 6.5 приведена совмещенная таблица для автомата Мили. На рисунке 6.6 приведена совмещенная таблица переходов для автомата Мура.

	x 1	x 2	…	x m
a 1	a 2 /y 1	a 1 /y 3	…	a 2 /y 1
a 2	a n-1 /y n-1	a 3 /y 2	…	a 1 /y n-1
…			…
a n	-	a n /y 1	…	a 2 /y 2

Рисунок 6.5 – Совмещенная таблица переходов и выходов автомата Мили

	x 1	x 2	…	x m	Y
a 1	a 2	a 1	…	a 2	y 2
a 2	a n-1	a 3	…	a 1	y 1
…			…
a n	-	a n	…	a 2	y 2

Рисунок 6.6 – Совмещенная таблица переходов автомата Мура
7.2 Графический способ задания цифровых автоматов
При графическом способе автомат задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины a m , задает переход в автомате из состояния a m в состояние a s . В начале этой дуги записывается входной сигнал X f X, вызывающий данный переход a s =(a m ,x f). Для графа автомата Мили выходной сигнал y g Y, формируемый на переходе, записывается в конце дуги, а для автомата Мура - рядом с вершиной a m , отмеченной состоянием a m , в котором он формируется. Если переход в автомате из состояния a m в состояние a s производится под действием нескольких входных сигналов , то дуге графа, направленной из a m в a s , приписываются все эти входные и соответствующие выходные сигналы. Граф С-автомата содержит выходные сигналы двух типов и они обозначаются на графе как на графах соответствующих автоматов. Граф автомата Мура представлен на рисунке 6.7, а автомата Мили – на рисунке 6.8.

y 2

Рисунок 6.7 –Графическое представление автомата Мура

Рисунок 6.8 –Графическое представление автомата Мили

8 Абстрактный синтез цифровых автоматов
Теория цифровых автоматов рассматривает абстрактный и структурный синтез цифровых автоматов. Абстрактный синтез не описывает внутреннего строения автомата, а дает описание взаимодействия с окружающей средой. К абстрактному синтезу относят:

• 
  определение входного, выходного и алфавита состояний, функции переходов и выходов ;
• 
  задание графов автомата и таблиц переходов и выходов;
• 
  минимизацию числа состояний

8.1 Структура цифрового автомата

Внутреннюю структуру цифрового автомата можно изобразить, как показано на рисунке 8.1.

Рисунок 8.1 – Структурная схема цифрового автомата.

Комбинационная схема №1 реализует переходы автомата из одного состояния в другое под воздействием входных сигналов. Схема проектируется исходя из закодированной таблицы переходов и подграфа переходов выбранного запоминающего элемента.

Блок памяти представляет собой набор триггеров, которые хранят разряды закодированного номера состояния. Количество триггеров зависит от количества состояний, в которых может находиться автомат. И вычисляется как:

N=log 2 M
где M – количество состояний, а N –количество триггеров
Комбинационная схема №2 реализует функцию выходов автомата и на ее выходе устанавливаются выходные значения автомата в соответствии с текущим состоянием автомата и входными значениями.

8.2 Минимизация числа состояний цифрового автомата
Часто при выполнении абстрактного синтеза вводятся избыточные состояния, эквивалентность которых не является очевидной. Избыточное количество состояний может привести к применению лишних триггеров, что усложнит КС1 и КС2. Поэтому очень важно выполнять минимизацию числа состояний перед его структурным синтезом.

Алгоритм минимизации основан на разбиении всего множества состояний на попарно непересекающиеся классы эквивалентных состояний и замене всего класса эквивалентности одним состоянием. Полученный в результате минимизированный автомат будет содержать столько состояний на сколько классов эквивалентности было разбито исходное множество состояний.

Определение Два состояния a s и a m являются эквивалентными, если
 (a s , E) =  (a m , E), где  - функция перехода, E – входное слово произвольной длины.

Другими словами, состояния эквивалентны, если в ответ на одни и те же входные слова вырабатывается одна и та же последовательность состояний, независимо от того в каком из двух состояний a s или a m находился автомат в начальный момент времени. Если два состояния эквивалентны , то одно состояние можно заменить на другое.

Кроме эквивалентных состояний существует понятие k-эквивалентных состояний: 1-эквивалентные, 2-эквивалентные и т.д.

Определение Два состояния a s и a m являются k - эквивалентными, если
 (a s , E k ) =  (a m , E k ), где  - функция перехода, E k – входное слово длины k .
Алгоритм минимизации:

1. 
   Находится последовательно разбиения П 1 , П 2 , … П К, П К+1 состояний автомата до тех пор пока на каком-то К+1 шаге П К.+1 станет равно П К. В этом случае полученное к-эквивалентное разбиение будет представлять собой полностью эквивалентные классы.
2. 
   В каждом классе эквивалентности выбирают по одному состоянию, которые образуют новое множество состояний минимизированного автомата.
3. 
   Для переопределения функций переходов и выходов вычеркивают строки, которые соответствую состояниям , не вошедшим в новое множество состояний минимизируемого автомата, а в остальных строка таблицы переходов все состояния заменяются на им эквивалентные состояния, которые вошли в новое множество.
4. 
   Если множество состоит из одного состояние, то у него нет эквивалентных состояний. Если все состояния входят в отдельные множества из одного состояния, то автомат нельзя минимизировать.
5. 
   Разбиение на множества начинается с 0-эквивалентного класса. В данном случае в одни множества попадают состояния с одинаковыми выходными сигналами.

Имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного алфавита , на выходе оно выдаёт символы (в общем случае) другого алфавита.

Формально абстрактный автомат определяется как пятерка

$\backslash boldsymbol\{A\; =\; (S,\; X,\; Y,\; \backslash delta,\; \backslash lambda)\}$

Ограничение числа параметров абстрактного автомата определило такое понятие как конечный автомат .

Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата $\backslash boldsymbol\{s\_1s\_2s\_3...\}$ и последовательности выходных символов $\backslash boldsymbol\{y\_1y\_2y\_3...\}$, которые для последовательности символов $\backslash boldsymbol\{x\_1x\_2x\_3...\}$ разворачиваются в моменты дискретного времени t = 1, 2, 3, … Моменты дискретного времени получили название тактов.

Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений: $\backslash boldsymbol\{s(t+1)=\backslash delta(s(t),x(t));\}$

$\backslash boldsymbol\{y(t)=\backslash lambda(s(t),x(t)).\}$

Для уточнения свойств абстрактных автоматов введена классификация .

Абстрактные автоматы образуют фундаментальный класс дискретных моделей как самостоятельная модель, и как основная компонента машин Тьюринга , автоматов с магазинной памятью , конечных автоматов и других преобразователей информации.

Напишите отзыв о статье "Абстрактный автомат"

Отрывок, характеризующий Абстрактный автомат

Государь с улыбкой обратился к одному из своих приближенных, указывая на молодцов апшеронцев, и что то сказал ему.

Кутузов, сопутствуемый своими адъютантами, поехал шагом за карабинерами.
Проехав с полверсты в хвосте колонны, он остановился у одинокого заброшенного дома (вероятно, бывшего трактира) подле разветвления двух дорог. Обе дороги спускались под гору, и по обеим шли войска.
Туман начинал расходиться, и неопределенно, верстах в двух расстояния, виднелись уже неприятельские войска на противоположных возвышенностях. Налево внизу стрельба становилась слышнее. Кутузов остановился, разговаривая с австрийским генералом. Князь Андрей, стоя несколько позади, вглядывался в них и, желая попросить зрительную трубу у адъютанта, обратился к нему.
– Посмотрите, посмотрите, – говорил этот адъютант, глядя не на дальнее войско, а вниз по горе перед собой. – Это французы!
Два генерала и адъютанты стали хвататься за трубу, вырывая ее один у другого. Все лица вдруг изменились, и на всех выразился ужас. Французов предполагали за две версты от нас, а они явились вдруг, неожиданно перед нами.
– Это неприятель?… Нет!… Да, смотрите, он… наверное… Что ж это? – послышались голоса.
Князь Андрей простым глазом увидал внизу направо поднимавшуюся навстречу апшеронцам густую колонну французов, не дальше пятисот шагов от того места, где стоял Кутузов.
«Вот она, наступила решительная минута! Дошло до меня дело», подумал князь Андрей, и ударив лошадь, подъехал к Кутузову. «Надо остановить апшеронцев, – закричал он, – ваше высокопревосходительство!» Но в тот же миг всё застлалось дымом, раздалась близкая стрельба, и наивно испуганный голос в двух шагах от князя Андрея закричал: «ну, братцы, шабаш!» И как будто голос этот был команда. По этому голосу всё бросилось бежать.
Смешанные, всё увеличивающиеся толпы бежали назад к тому месту, где пять минут тому назад войска проходили мимо императоров. Не только трудно было остановить эту толпу, но невозможно было самим не податься назад вместе с толпой.
Болконский только старался не отставать от нее и оглядывался, недоумевая и не в силах понять того, что делалось перед ним. Несвицкий с озлобленным видом, красный и на себя не похожий, кричал Кутузову, что ежели он не уедет сейчас, он будет взят в плен наверное. Кутузов стоял на том же месте и, не отвечая, доставал платок. Из щеки его текла кровь. Князь Андрей протеснился до него.
– Вы ранены? – спросил он, едва удерживая дрожание нижней челюсти.
– Раны не здесь, а вот где! – сказал Кутузов, прижимая платок к раненой щеке и указывая на бегущих. – Остановите их! – крикнул он и в то же время, вероятно убедясь, что невозможно было их остановить, ударил лошадь и поехал вправо.