6 Основные понятия и определения теории абстрактных авто­матов (лекция №9)



жүктеу 416.83 Kb.
бет1/3
Дата17.04.2016
өлшемі416.83 Kb.
  1   2   3
: media
media -> Эффективность применения коллоидной фитоформулы ангиомега комплекс в кардиологии
media -> Инструкция по настройке параметров Интернет и ммс на телефонах U8230
media -> Қазақстан Республикасы Ішкі істер министрлігінің ақпараттық жүйелерін «электрондық үкіметтің» шлюзімен біріктіру мүмкіндіктерін зерделеу жөніндегі жұмыс жоспары
media -> І. Жаңаөзен қалалық білім бөлімінің 2013 жылғы жұмысының қортындысы
media -> Күндізгі оқу түрі
media -> Қазақстан Республикасы Мәдениет және ақпарат министрлігінің кейбір мәселелері

Оглавление


Оглавление 1


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

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

  1. A={a1, a2, ... ,am} – алфавит состояний – множество состояний, в которых может находиться проектируемый цифровой автомат. Количество состояний играет важную роль при реализации ЦА. Чем больше состояний, тем больше требуется запоминающих элементов(триггеров) для построения ЦА.

  2. X={x1, x2, ... ,xf} – алфавит входных значений – множество значений, которые могут поступать на вход ЦА. Например, если у автомата двухразрядный двоичный вход, то элементами алфавита могут быть 00, 01, 10 и 11.

  3. Y={y1, y2, ..., yg} – алфавит выходных значений – множество значений, которые могут быть установлены на выходе ЦА.

  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. ai 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), x(t)], a(t) A, y(t) Y.

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

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

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



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

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



  1. полностью определенные и частичные;

  2. детерминированные и вероятностные;

  3. синхронные и асинхронные;

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

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

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

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

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

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

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

Абстрактный автомат называется конечным, если конечны множества А = {a1, a2, ..., am}, Z = {z1, z2, ..., zf}, W = {w1, w2, ..., wg}. Автомат носит название инициального, если в нем выделено начальное состояние a1.
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, ...
Выходной сигнал Uh=2(am ) выдается все время, пока автомат находится в состоянии am. Выходной сигнал Wg=1( am, zf ) выдается во время действия входного сигнала Zf при нахождении автомата в состоянии am.
7 Способы описания и задания автоматов (лекция№10)
Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, X, Y, , , а1 ). Множества А, X, Y описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций  и  (следовательно и всего автомата в целом) наибольшее распространение получили табличный и графиче­ский.
7.1 Табличный способ описания цифровых автоматов

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



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




x1

x2



xm

a1

a2

a1



a2

a2

an-1

a3



a1














an

-

an



a2

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




x1

x2



xm

a1

y1

y3



y1

a2

yn-1

y2



yn-1














an

-

y1



y2

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

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




x1

a1

y1

a2

yn-1






an

y2

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





x1

x2



xm

a1

a2/y1

a1/y3



a2/y1

a2

an-1/yn-1

a3/y2



a1/yn-1














an

-

an /y1



a2/y2

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





x1

x2



xm

Y

a1

a2

a1



a2

y2

a2

an-1

a3



a1

y1

















an

-

an



a2

y2

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


y2

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



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


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

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

  • задание графов автомата и таблиц переходов и выходов;

  • минимизацию числа состояний


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

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



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


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

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

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

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

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



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

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



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

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

  1. Находится последовательно разбиения П1, П2, … ПК, ПК+1 состояний автомата до тех пор пока на каком-то К+1 шаге ПК.+1 станет равно ПК. В этом случае полученное к-эквивалентное разбиение будет представлять собой полностью эквивалентные классы.

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

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

  4. Если множество состоит из одного состояние, то у него нет эквивалентных состояний. Если все состояния входят в отдельные множества из одного состояния, то автомат нельзя минимизировать.

  5. Разбиение на множества начинается с 0-эквивалентного класса. В данном случае в одни множества попадают состояния с одинаковыми выходными сигналами.


  1   2   3


©netref.ru 2017
әкімшілігінің қараңыз

    Басты бет