С-автомат

Под абстрактным С-автоматом понимается математическая модель цифрового устройства, задаваемого вектором S_C=< A, X, Y, U, d, l ₁, l ₂, a ₁>

В этом векторе:

А – обозначает внутренний алфавит;

Х – обозначает входной алфавит;

Y – обозначает выходной алфавит типа 1 (как у автомата Мили);

U ={ u ₁,… u _r,… u _R} – обозначает выходной алфавит типа 2 (как у автомата Мура);

d: A × X®A, функция переходов, реализующая сюрьективное отображение

d: А × Х на А;

l ₁: А × Х→Y – функция выходов, реализующая сюръективное отображение l ₁: А × Х на Y;

l ₂: А→U – функция выходов, реализующая сюръективное отображение l ₂: А→U;

a ₁ – обозначает начальное состояние автомата.

С-автомат содержит выходные функции двух типов: типа 1 и типа 2. Т.е. он является сочетанием элементов автоматов и Мили, и Мура.

Функционирование С-автомата задается уравнениями

a (t +1)= d [ a (t), x (t)];

y (t)= l ₁[ a (t), x (t)];

u (t)= l ₂[ a (t)];

t =0,1,2,…

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

u ₁ – загорается кнопка «пуск».

Рисунок 4.5 – Граф переходов абстрактного С-автомата по продаже жетонов

Здесь за основу взят автомат Мили и добавился выходной сигнал по типу автомата Мура u ₁. Как только автомат попадает в состояние а ₂ (или а ₃, или а ₄) должна загораться кнопка «пуск». А когда кнопка «пуск» будет нажата, будет происходить переход в состояние а ₁ и выдача жетонов со сдачей.

Автоматы называются дискретными или цифровыми, так как они функционируют во времени дискретно или прерывно (по тактам).

Существуют автоматы синхронные и асинхронные.

Интервалы времени в синхронных автоматах фиксированы и генерируются специальным генератором синхроимпульсов. В асинхронных автоматах моменты дискретного времени определяются изменением состояния памяти или входных сигналов. В компьютерах применяются синхронные цифровые автоматы.

Автомат называется конечным (Finite state machine - FSM), если конечны множества A, X и Y. В дальнейшем будут рассматриваться только конечные автоматы и термин «конечный» может опускаться.

Автомат называется полностью определенным, если область определения функций переходов d и функций выхода l = D _d= D _l= А × Х. Другими словами, область определения d и l совпадают с множеством А × Х – множеством всевозможных пар (a _m, x _f). У не полностью определенного, или частичного, автомата функции d и l определены не для всех пар (a _m, x _f) Î А × Х.

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