1. Типы автоматов и способы их задания

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

1.1. Типы автоматов

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

В зависимости от типа элементов, из которых построен автомат, различают два основных типа автоматов:

комбинационные схемы или автоматы без памяти;

 автоматы с памятью или последовательностные схемы.

Обобщенный сигнал Y на выходах комбинационной схемы является, соответственно, комбинацией сигналов y_j на отдельных её выходах. Выходной сигнал Y зависит только от входного сигнала Х, т.е. только от комбинации сигналов на входах схемы:

В соответствии с (1.1) комбинационная схема с несколькими входами и несколькими выходами может быть представлена в обобщенном виде так, как это показано на рис. 1.2.

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

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

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

На рис.1.3 приняты следующие обозначения:

 Эп_r - элемент памяти r автомата, r = 1, 2, … m;

 X_t - обобщенный входной сигнал в текущем такте;

 x_i - сигнал на входе i автомата, i = 1. 2. … n;

 Y_t - обобщенный входной сигнал в текущем такте;

 Yj - сигнал на выходе j автомата, j = 1. 2. … k;

 Q_t - состояние автомата в текущем такте;

 q_m - состояние элемента памяти m , m = 1, 2, … m.

Информация, записанная в элементах памяти автомата, называется состоянием (или внутренним состоянием) автомата. Состояние автомата в целом (Q) определяется состоянием отдельных элементов памяти (q_i). Основная особенность автоматов с памятью состоит в том, что сигнал на выходе автомата зависит как от входного сигнала, так и от состояния автомата.

Таким образом

Y_t = Y( X_t, Q_t ) (1.2)

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

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

Содержательно автомат можно охарактеризовать как устройство, имеющее входы и выходы и находящееся в каждый из моментов дискретного времени, в одном из состояний (Q_t).

Обобщенная структура автомата с памятью показана на рис.1.4, где входные и выходные сигналы, а также состояние автомата, представлены в обобщенном виде.

При работе автомата в каждом такте кроме выходного сигнала формируется также новое состояние, которое зависит от входного сигнала и текущего состояния автомата:

Из соотношения (1.3) видно, что после начала работы автомата из состояния Q₀ его последующие состояния связаны с входными сигналами следующим образом:

 Q₁ = Q ( X₁, Q₀ ), т.е. Q₁ зависит от сигнала X₁ и состояния Q₀ ;

 Q₂ = Q ( X₂, Q₁ ), т.е. Q₂ зависит от сигнала X₂ и состояния Q₁ ;

Но так как Q₁ = Q ( X₁, Q₀ ), то Q₂ = Q (X₁, X2, Q₁ ), т.е. Q₂ зависит от сигналов X₁ , X₂ и состояния Q₁ .

Аналогично можно показать, что состояние Q₃ зависит от сигналов X₁,X₂,X₃ и состояния Q₂ и т.д. В приведенных выше рассуждениях индексы при X и Q означают номера тактов.

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

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

В качестве примера рассмотрим два варианта построения схемы управления кодовым замком. Пусть кодовый замок имеет десять кнопок, пронумерованных цифрами от 0 до 9. И пусть, например, схема управления должна выдать сигнал на открытие замка при одновременном нажатии только кнопок 3, 5 и 8.

Если принять, что порядок нажатия кнопок безразличен, то схема управления должна реагировать только на определенную комбинацию нажатых кнопок (в данном примере на комбинацию 3, 5, 8). В этом случае такая схема управления может быть построена в виде комбинационной схемы.

Если заданы не только комбинация нажатых кнопок, но и последовательность их нажатия (например, замок должен открываться только при нажатии сначала кнопки 5, затем кнопки 3 и затем кнопки 8), то схема управления замком должна запоминать, в каком порядке были нажаты кнопки. В этом случае в состав схемы должны входить элементы памяти. Поэтому такая схема управления представляет собой автомат с памятью.

Таким образом, схема управления замком, выполненная по второму варианту, является более сложной, но при этом она обеспечивает более высокую степень защиты замка.

Существует большое количество различных структур автоматов. В общем случае любой автомат может иметь различную структуру. Однако структуру любого автомата можно преобразовать к одной из двух типовых структур:
 Автомат 1-го рода или автомат Мили.

 Автомат 2-го рода или автомат Мура.

Структура автомата Мили представлена на рис. 1.5.

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

Первая комбинационная схема (в дальнейшем будем обозначатьее КС1) имеет две группы входов. Одна группа входов является входами автомата в целом (x₁, x₂, …, x_{n ).} На другую группу входов поступают сигналы из памяти автомата (q_t¹, q_t², …, q_t^k _)., т.е. состояние автомата. По отношению к автомату в целом эти сигналы являются внутренними. На выходах схемы КС1 формируются сигналы (q_t+1¹,q_t+1²,…,q_t+1^k)_, которые поступают на входы элементов памяти (ЭП_r).



X₁

X₂

X_n

После записи в память эти сигналы в следующем такте будут представлять собой следующее состояние автомата (Q_t+1). Таким образом схема КС1 является схемой формирования следующего состояния автомата.

Вторая комбинационная схема (КС2) называется выходным преобразователем и служит для формирования выходных сигналов автомата (y₁, y₂, …, y_{m ).} На ее входы поступают те же сигналы, что и на входы схемы КС1. Поэтому выходные сигналы в автомате Мили зависят как от состояния, так и от входных сигналов, поступающих в данном такте. Обобщенная структура автомата Мили имеет вид, представленный на рис.1.6.

Работа автомата Мили описывается в общем виде уравнениями переходов и выходов:

Уравнение (функция) переходов Q_t+1=Q(X_t, Q_t) определяет условия перехода автомата из одного состояния в другое. Это уравнение задает логику работы комбинационной схемы КС1.

Уравнение (функция) выходов Y_t=Y(X_t,Q_t ) определяет условия формирования определенных выходных сигналов. Это уравнение задает логику работы комбинационной схемы КС2.

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

Автомат Мура имеет структуру, показанную на рис. 1.7.

Эта структура внешне очень незначительно отличается от структуры автомата Мили. Как видно на рис.1.7, это отличие заключается в том, что в автомате Мура входной сигнал не поступает на комбинационную схему КС2 (схему формирования выходов).

Работа автомата Мура описывается следующими уравнениями переходов и выходов:

Y_t = Y( Q_t ) ; (1.5)

Q_{t + 1} = Q ( X_t, Q_t).
Из уравнений (1.5) видно, что выходной сигнал автомата Мура зависит только от текущего состояния и не зависит от входного сигнала в данном такте. Следует особо отметить, что выходной сигнал зависит от входных сигналов, поступивших в предыдущих тактах, поскольку от них зависит текущее состояние. Таким образом, выходной сигнал автомата Мура задержан на один такт по отношению к входному сигналу

Иногда выходные сигналы автомата Мура совпадают с сигналами состояний. В этом случае автомат не имеет комбинационной схемы КС2 и называется автоматом без выходного преобразователя. Обобщенная структура такого автомата показана на рис. 1.8.

Алгоритм работы автомата Мура без выходного преобразователя описывается следующими уравнениями переходов и выходов:

Задать автомат – значит описать алгоритм его работы. Автомат считается заданным, если известны:

 алфавит входных сигналов X = {X₁, X₂, … , X_i, … , X_n};

 алфавит выходных сигналов Y = {Y₁, Y₂, … , Y_j, … , Y_m};

 алфавит состояний Q = {Q₁, Q₂, … , Q_r, … , Q_k};

 начальное состояние Q₀;

 функция переходов Q_{t + 1} = Q ( X_t, Q_t);

 функция выходов Y_t = Y( X_t, Q_t ).

В приведенном перечне объектов основными являются функции переходов и выходов. Для задания автоматов используются следующие способы:

 словесное описание;

 графическое описание;

 табличное описание;

 аналитическое описание.

Словесное описание используется на начальном этапе задания автомата, а его элементы находят применение в других способах. Недостатком словесного описания является его громоздкость и возможная неоднозначность.

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

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

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

Отметим, что при синтезе автоматов обычно на различных этапах используются различные способы описания. Кроме того, задание автоматов Мили и Мура имеет некоторые особенности.

В качестве примера рассмотрим различные способы описания автомата с одним входом и одним выходом. На вход автомата поступает произвольная последовательность нулей и единиц. Автомат должен выдавать сигнал «1», если на вход поступает не менее двух символов «1» подряд. Такое задание можно считать упрощенным словесным заданием. Оно не связано с типом автомата. Другие способы описания рассмотрим отдельно для автоматов Мили и Мура.

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

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

Графы автоматов Мили и Мура, реализующих рассмотренный выше алгоритм, представлены на рис. 1.9.

а) б)

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

Функции переходов и выходов рассматриваемых автоматов имеют следующий вид:

для автомата Мили для автомата Мура

Количество функций переходов зависит от количества элементов памяти, количество функций выхода – от числа выходов. В данном примере автомат, синтезированный как автомат Мура, имеет два элемента памяти.

Укажите основное отличие автоматов с памятью от комбинационных схем по их составу.

Укажите основное отличие автоматов с памятью от комбинационных схем по логике их работы.

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

схемы ?

От чего зависит выходной сигнал автомата Мили ?

От чего зависит следующее состояние автомата ?

Чем отличаются структуры автоматов Мили и Мура?

Чем отличаются функции выходов автоматов Мили и Мура?

Можно ли по графу автомата определить тип автомата (автомат Мили

или Мура)?