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

Оглавление

1. 
   A={a₁, a₂, ... ,a_m} – алфавит состояний – множество состояний, в которых может находиться проектируемый цифровой автомат. Количество состояний играет важную роль при реализации ЦА. Чем больше состояний, тем больше требуется запоминающих элементов(триггеров) для построения ЦА.
   
2. 
   X={x₁, x₂, ... ,x_f} – алфавит входных значений – множество значений, которые могут поступать на вход ЦА. Например, если у автомата двухразрядный двоичный вход, то элементами алфавита могут быть 00, 01, 10 и 11.
   
3. 
   Y={y₁, y₂, ..., 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), x(t)], a(t) A, y(t) Y.

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

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

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

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

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

К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов : автомат, находя­щийся в некотором состоянии 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₁, a₂, ..., a_m}, Z = {z₁, z₂, ..., z_f}, W = {w₁, w₂, ..., w_g}. Автомат носит название инициального, если в нем выделено начальное состояние a₁.
6.3 Разновидности цифровых автоматов
На практике наибольшее распространение получили два класса автоматов - автоматы Мили (Mealy) и Мура (Moore).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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