Синтез автомата Мили по граф-схеме

Синтез автомата Мили по граф-схеме — это метод построения функциональной схемы автомата.

Описание

Автомат Мили (Mealy machine) — кортеж из 6 элементов, включающий: множество внутренних состояний S (внутренний алфавит); начальное состояние S₀; множество входных сигналов X (входной алфавит); множество выходных сигналов Y (выходной алфавит); функция переходов X; функция выходов Y.

Определение

Автомат Мили — конечный автомат, выходная последовательность которого зависит от состояния автомата и входных сигналов, в отличие от автомата Мура. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ). В вершины графа автомата Мили записываются выходящие сигналы, а дугам графа приписывают условие перехода из одного состояния в другое, а также входящие сигналы. Назван именем Джорджа Мили, учёного в области математики и компьютерных наук, придумавшего этот автомат.

Обозначения

ГСА — граф-схема автомата;

ФСА — функциональная схема автомата;

a₀ — вход вершины следующей за оператором — начальное и конечное состояние автомата;

a_m — вход вершины следующей за оператором — исходное состояние перехода;

a_s — вход вершины следующей за оператором — конечное состояние перехода;

a_m→a_s — переход из одного состояния в другое;

X(a_m,a_s) — логическое условие перехода;

Y(a_m,a_s) — функция выходов (микрокоманда);

Z_i — промежуточные функции;

DC — дешифратор состояний автомата;

D_i — значение на D-триггере.

Примеры:

Пример 1

Синтез автомата Мили по ГСА (рис.1).

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Рис.1. ГСА автомата Мили с узлами.

Разметка состояний

В автомате Мили входу каждой операторной вершины соответствует состояние автомата. Микрокоманда y₁y₂ вырабатывается УА при завершении его работы по ГСА. y₁y₂ — соответствует событию «операция выполнена». Искусственно введём y₁y₂ при любых переходах в начальное (конечное) состояние а₀. Переход из состояния a_m в состояние a_s — это переход из одной операторной вершины в другую при выполнении логический условий X(a_m,a_s) на пути из a_m в a_s. Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию a₀.

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Рис.2. Размеченная ГСА автомата Мили.

Построение прямой таблицы переходов 1

Прямая таблица переходов строится по размеченной ГСА (рис.1). В ней указываются все возможные пути переходов из состояния а_m в состояние а_s, условия при которых переход из а_m в а_s, происходит по данному пути (X(a_m,a_s)), микрокоманда (Y(a_m,a_s)), вырабатывается автоматом на данном переходе. Все эти переходы описываются в прямой таблице переходов. В столбце X(a_m,a_s) единица записывается тогда, когда a_m в a_s переход осуществляется всегда.

Таблица 1.

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Кодирование состояний

Произведём кодирование узлов. УА с жесткой логикой имеет память состояний, которая обычно выполнена на D- или RS- триггерах, синхронизируемых фронтом. Каждое состояние кодируется двоичным числом. Минимальное количество триггеров для памяти состояний должно быть больше или равно log2 (количество состояний автомата). В данном примере |А| - количество состояний автомата = 5, поэтому число элементов памяти = 3. Коды состояний: k(a₀)=100; k(a₁)=011; k(a₂)=010; k(a₃)=001; k(a₄)=000.

Построение обратной структурной таблицы 2

Обратная структурная таблицы автомата строится из прямой таблицы переходов упорядочиванием строк по полю а_s и добавлением столбцов k(a_m), k(a_s), F(a_m,a_s). В столбце F(a_m,a_s) — записываются значения сигналов управления элементами памяти. В данном примере в качестве элементов памяти выбраны D-триггера. Их состояние зависит от значения управляющего сигнала D на входе D-триггера.

Таблица 2.

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Построим по таблице 2 граф переходов (см.рис.3).

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Рис.3. Граф переходов.

Запись функции выходов и переходов автомата

В функциях выходов y_i= f_i(a_m,X(a_m,a_s)), записанных в виде ДНФ, описываются условия формирования автоматом микрокоманды y_i; a_m — исходное состояние, X(a_m,a_s) — условия перехода из a_m в a_s. В функциях переходов D_i= f_i(a_m,X(a_m,a_s)), также записанных в виде ДНФ, описываются значения сигналов управления элементами памяти, обеспечивающих переход из состояния a_m в a_s. Функции выходов и переходов могут быть минимизированы с использованием карт Карно или законов булевой алгебры. По обратной структурной таблице запишем функции для Y_i и D_i.

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Построение ФСА автомата Мили

В качестве элементов памяти использованы D-триггера T₁ и T₀. DC — дешифратор состояний автомата. Z_i — промежуточные функции — термы из функций. Их введение позволило упростить схему автомата.

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Рис.4. ФСА автомата Мили на жёсткой логике.

Пример 2

Синтез автомата Мили по ГСА (рис.5).

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Рис.5. ГСА автомата Мили с узлами.

Разметка состояний

В автомате Мили входу каждой операторной вершины соответствует состояние автомата. Микрокоманда y₁y₂ вырабатывается УА при завершении его работы по ГСА. y₁y₂ — соответствует событию «операция выполнена». Искусственно введём y₁y₂ при любых переходах в начальное (конечное) состояние а₀. Переход из состояния a_m в состояние a_s — это переход из одной операторной вершины в другую при выполнении логический условий X(a_m,a_s) на пути из a_m в a_s. Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию a₀.

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Рис.6. Размеченная ГСА автомата Мили.

Построение прямой таблицы переходов 3

Прямая таблица переходов строится по размеченной ГСА (рис.5). В ней указываются все возможные пути переходов из состояния а_m в состояние а_s, условия при которых переход из а_m в а_s, происходит по данному пути (X(a_m,a_s)), микрокоманда (Y(a_m,a_s)), вырабатывается автоматом на данном переходе. Все эти переходы описываются в прямой таблице переходов. В столбце X(a_m,a_s) единица записывается тогда, когда a_m в a_s переход осуществляется всегда.

Таблица 3.

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Кодирование состояний

Произведём кодирование узлов. УА с жесткой логикой имеет память состояний, которая обычно выполнена на D- или RS- триггерах, синхронизируемых фронтом. Каждое состояние кодируется двоичным числом. Минимальное количество триггеров для памяти состояний должно быть больше или равно log2 (количество состояний автомата). В данном примере |А| - количество состояний автомата = 4, поэтому число элементов памяти = 2. Коды состояний: k(a₀)=11; k(a₁)=10; k(a₂)=01; k(a₃)=00.

Построение обратной структурной таблицы 4

Обратная структурная таблицы автомата строится из прямой таблицы переходов упорядочиванием строк по полю а_s и добавлением столбцов k(a_m), k(a_s), F(a_m,a_s). В столбце F(a_m,a_s) — записываются значения сигналов управления элементами памяти. В данном примере в качестве элементов памяти выбраны D-триггера. Их состояние зависит от значения управляющего сигнала D на входе D-триггера.

Таблица 4.

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Построим по таблице 4 граф переходов (см.рис.7).

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Рис.7. Граф переходов.

Запись функции выходов и переходов автомата

В функциях выходов y_i= f_i(a_m,X(a_m,a_s)), записанных в виде ДНФ, описываются условия формирования автоматом микрокоманды y_i; a_m — исходное состояние, X(a_m,a_s) — условия перехода из a_m в a_s. В функциях переходов D_i= f_i(a_m,X(a_m,a_s)), также записанных в виде ДНФ, описываются значения сигналов управления элементами памяти, обеспечивающих переход из состояния a_m в a_s. Функции выходов и переходов могут быть минимизированы с использованием карт Карно или законов булевой алгебры. По обратной структурной таблице запишем функции для Y_i и D_i.

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Построение ФСА автомата Мили

В качестве элементов памяти использованы D-триггера T₁ и T₀. DC — дешифратор состояний автомата. Z_i — промежуточные функции — термы из функций. Их введение позволило упростить схему автомата.

Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения

Рис.8. ФСА автомата Мили на жёсткой логике.

Другие алгоритмы:

• алгоритм метода математической индукции;
• алгоритмы в арифметике;
• алгоритмы перевода чисел;
• комбинаторные алгоритмы;
• алгоритм сортировки;
• алгоритм определения мест;
• логистические алгоритмы;
• алгоритмы решения транспортных задач;
• алгоритмы численных методов;
• алгоритмы построенные с помощью машины Поста;
• алгоритмы построенные с помощью машины Тьюринга;
• алгоритм синтеза автомата Мили;
• алгоритм синтеза автомата Мура.

Ссылки

• https://ru.wikipedia.org/wiki/Автомат_Мили
• Воронцов И.В. Курс лекций по предметам теория автоматов и системотехника. СамГТУ. 2012-2013г.
• Участник:Logic-samara