logo
Ответы на вопросы экз

30. Автомат Мура

Два типа автоматов получили наибольшее распространение на практике: автомат Мили и Мура, названные так по имени впервые исследовавших эти модели американских ученых G.H. Mealy и E.F. Moore.

Автомат Мура

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

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

y(t)=2[a(t)];

t=0,1,2,….

Рассмотрим в качестве примера упрощенный вариант автомата, продающего в метро жетоны, который был рассмотрен раньше. Состояния, входные и выходные сигналы те же. Но выходные сигналы прописаны в вершинах (рис.4.4). Это означает, что выходной сигнал будет формироваться не во время перехода из состояния в момент времени t в состояние в момент времени t+1, а в момент, когда автомат перейдет в состояния в момент времени t. Например, как только автомат перейдет в состояние a5 будет формироваться выходной сигнал у1.

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

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

Выходная функция автомата Мили зависит как от внутреннего состояния, так и от входного сигнала.

31. С-автомат

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

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

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

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

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

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

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

: А×Х на А;

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

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

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

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

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

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

y(t)=1[a(t), x(t)];

u(t)=2[a(t)];

t=0,1,2,…

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

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

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

Здесь за основу взят автомат Мили и добавился выходной сигнал по типу автомата Мура u1. Как только автомат попадает в состояние а2 (или а3, или а4) должна загораться кнопка «пуск». А когда кнопка «пуск» будет нажата, будет происходить переход в состояние а1 и выдача жетонов со сдачей.

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

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

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

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

Автомат называется полностью определенным, если область определения функций переходов и функций выхода =D=D=А×Х. Другими словами, область определения и совпадают с множеством А×Х – множеством всевозможных пар (am, xf). У не полностью определенного, или частичного, автомата функции и определены не для всех пар (am, xf) А×Х.

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