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

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

Описание

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

Определение

Автомат Мура — абстрактный автомат второго рода — конечный автомат, выходное значение сигнала в котором зависит лишь от текущего состояния данного автомата, и, не зависит напрямую, в отличие от автомата Мили, от входных значений. Автомат Мура назван в честь описавшего его свойства Эдварда Ф. Мура.

Обозначения

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

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

b₀ — операторная вершина — начальное и конечное состояние автомата;

b_m — операторная вершина — исходное состояние перехода;

b_s — операторная вершина — конечное состояние перехода;

ө_s — узел — дополнительная операторная вершина для упрощения ГСА;

b_m→b_s — переход из одной операторной вершины в другую;

b_m→ө_s, ө_m→b_s, ө_m→ө_s — дополнительные переходы;

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

S_i — значение на S-триггере;

R_i — значение на R-триггере.

Примеры:

Пример 1

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

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

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

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

В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния b_m в состояние b_s — это переход из одной операторной вершины в другую при выполнении логический условий X(b_m,b_s) на пути из b_m в b_s. Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию b₀. Узлы ө используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются.

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

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

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

Отличительная особенность: в данном примере в ГСА введены узлы ө. В ГСА с узлами возможны переходы четырех видов: b_m→b_s, b_m→ө_s, ө_m→b_s, ө_m→ө_s. Все эти переходы описываются в прямой таблице переходов.

Таблица 1.

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

В столбце X(b_m,b_s) единица записывается тогда, когда b_m в b_s переход осуществляется всегда.

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

Произведём кодирование узлов (узлы ө не кодируются). В данном примере — автомат имеет четыре состояния (кроме начального), для кодирования необходимо не менее трёх двоичных разрядов. Память состояний на RS триггерах. Коды состояний: k(b₀)=000; k(b₁)=001; k(b₂)=010; k(b₃)=011; k(b₄)=100.

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

Вначале описываем переходы в узлы, затем остальные переходы автомата.

Таблица 2.

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

Если переход в некоторое состояние b_s происходит из узла ө, то в автомате с памятью на RS триггерах значения R_i и S_i в обратной структурной таблице записываются с учетом кодов состояний b_m из которых был переход в узел ө.

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

Рис.3. Схема определения значений R_i и S_i.

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

По обратной структурной таблице запишем функции для ө, Y_i, R_i и S_i.

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

Легко заметить, что использование узлов в ГСА автомата Мура позволило значительно упростить функции выходов и переходов.

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

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

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

Пример 2

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

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

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

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

В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния b_m в состояние b_s — это переход из одной операторной вершины в другую при выполнении логический условий X(b_m,b_s) на пути из b_m в b_s. Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию b₀. Узлы ө используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются.

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

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

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

Отличительная особенность: в данном примере в ГСА введены узлы ө. В ГСА с узлами возможны переходы четырех видов: b_m→b_s, b_m→ө_s, ө_m→b_s, ө_m→ө_s. Все эти переходы описываются в прямой таблице переходов.

Таблица 3.

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

В столбце X(b_m,b_s) единица записывается тогда, когда b_m в b_s переход осуществляется всегда.

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

Произведём кодирование узлов (узлы ө не кодируются). В данном примере — автомат имеет три состояния (кроме начального), для кодирования необходимо не менее двух двоичных разрядов. Память состояний на RS триггерах. Коды состояний: k(b₀)=00; k(b₁)=01; k(b₂)=01; k(b₃)=11.

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

Вначале описываем переходы в узлы, затем остальные переходы автомата.

Таблица 4.

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

Если переход в некоторое состояние b_s происходит из узла ө, то в автомате с памятью на RS триггерах значения R_i и S_i в обратной структурной таблице записываются с учётом кодов состояний b_m из которых был переход в узел ө.

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

Рис.7. Схема определения значений R_i и S_i.

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

По обратной структурной таблице запишем функции для ө, Y_i, R_i и S_i.

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

Легко заметить, что использование узлов в ГСА автомата Мура позволило значительно упростить функции выходов и переходов.

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

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

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

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

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

Ссылки

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