AXA – функция переходов a(t+1)=(x(t),a(t)). Функция переходов определяет, в какое состояние a(t+1) перейдет автомат под воздействием входного сигнала x(t), если в текущий момент времени автомат находится в состоянии a(t).
Скачать 416.93 Kb.
|
ОглавлениеОглавление 1 6 Основные понятия и определения теории абстрактных автоматов (лекция №9) Цифровой (дискретный) автомат (ЦА) – устройство, которое осуществляет прием, хранение и/или преобразование дискретной информации по некоторому алгоритму. Примерами ЦА могут служить живые организмы, процессоры, бытовая техника калькуляторы – это реальные устройства, а также есть абстрактные, например, модели алгоритмов. ЦА относятся к последовательным устройствам. Этот класс устройств определяется тем, что значение выходов зависит не только от входных значений, но и от текущего состояния устройства. Т.е. вводится понятие – состояние. Для того чтобы хранить данные о состоянии, в котором находится устройство в ЦА используются запоминающие элементы – триггеры. ^ Цифровой автомат - устройство, характеризующееся набором внутренних состояний в которое оно попадет под воздействием команд заложенной в него программы. Переход автомата из одного состояния в другое осуществляется в определенный момент времени. Математической моделью ЦА (а в общем случае любого дискретного устройства) является так называемый абстрактный автомат, определенный как 6-компонентный кортеж: S=(A,X,Y,,,а1) у которого:
Под алфавитом здесь понимается непустое множество попарно различных символов. Элементы алфавита называются буквами, а конечная упорядоченная последовательность букв - словом в данном алфавите.  Рисунок 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), рассматривая его как "черный ящик", т.е. основное внимание уделяем поведению автомата относительно внешней среды. Понятие состояния в определении автомата введено в связи с тем, что часто возникает необходимость в описании поведения систем, выходы которых зависят не только от состояния входов в данный момент времени, но и от некоторой предыстории, т.е. от сигналов, которые поступали на входы системы ранее. Состояния как раз и соответствуют некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходной сигнал как функцию состояния и входа в данный момент времени. ^ Рассмотренные выше абстрактные автоматы можно разделить на:
Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов и функция выходов определены для всех пар ( 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. ^ На практике наибольшее распространение получили два класса автоматов - автоматы Мили (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. ^ Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, X, Y, , , а1 ). Множества А, X, Y описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций и (следовательно и всего автомата в целом) наибольшее распространение получили табличный и графический. ^ При табличном способе описания цифровых автоматов применяется два вида таблиц – таблица переходов и таблица выходов. ^ отображает функцию переходов. Строкам таблицы соответствуют состояния автомата, т.е. в таблице столько строк, сколько состояний у автомата. Столбцам таблицы соответствуют входные значения, которые могут поступать на входы ЦА, т.е. столбцом столько – сколько элементов во входном алфавите. На пересечении i-столбца и j-строки в ячейке таблицы указывается состояние в которое перейдет ЦА под воздействием входного сигнала xi (которому соответствует i-й столбец) из состояния aj (которому соответствует j-я строка). Таблица переходов приведена на рисунке 6.2
Рисунок 6.2 – Таблица переходов ЦА Таблица переходов имеет одинаковый вид как для автомата Мура, так и для автомата Мили. Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте не определенных состояний и выходных сигналов ставится прочерк. В таких автоматах выходной сигнал на каком-либо переходе всегда не определен, если неопределенным является состояние перехода ^ имеет такой же вид как и таблица переходов, только на пересечении i-столбца и j-строки в ячейке таблицы указывается выходное значение, которое сформирует ЦА под воздействием входного сигнала xi (которому соответствует i-й столбец) в состоянии aj (которому соответствует j-я строка). Таблица выходов автомата Мили приведена на рисунке 6.3
Рисунок 6.3 – Таблица выходов автомата Мили ^ состоит из одного столбца. Строкам таблицы соответствуют состояния автомата, т.е. в таблице столько строк, сколько состояний у автомата. Пример таблицы приведен на рисунке 6.4
Рисунок 6.4 – Таблица выходов автомата Мура В некоторых случаях вместо двух таблиц определяющих ЦА удобно применять совмещенную таблицу переходов и выходов. На рисунке 6.5 приведена совмещенная таблица для автомата Мили. На рисунке 6.6 приведена совмещенная таблица переходов для автомата Мура.
Рисунок 6.5 – Совмещенная таблица переходов и выходов автомата Мили
Рисунок 6.6 – Совмещенная таблица переходов автомата Мура |
Добавить документ в свой блог или на сайт
Похожие:
 | Для количественной и качественной оценки совпадения двух сигналов и (его смещенной копии ) вводится так называемая автокорреляци-онная... |  | Функция является четной- если для любого Х из области определения функции выполняется равенство f(X)=f(-X)Функция является нечетной-... |
| В данной статье проанализирована возможность применения физических фазовых переходов для экономики, а также предложен алгоритм определения... | | Исследовать функцию на четность(в условие вместо X подставить (-X) и, если результат совпадет с условием,то эта функция четная,если... |
| Кпд 93 %, функция последнего цикла циркуляции на стороне обогрева, функция последнего цикла вентиляции, противоблокировочная система... | | Дана функция времени, состоящая из прямоугольных импульсов высотой h и шириной, повторяющиеся с частотой. Это функция с периодом |
| Эта функция показывает степень сходства между сигналом и его сдвинутой копией. Чем больше эта функция, тем больше сходство | | Вашему вниманию представляется вендинговый автомат для выпрямления волос, который имеет невероятный коммерческий потенциал, является... |
| Если хотя бы раз использовалась функция сигнала (в течение 20 секунд), а секундомер в течение 1 часа | | «Аэр пит Откл Аккум.» находится в положении «Откл», а автомат защиты сети «Зажигание» выключен (находится в нижнем положении) |