Построить каноническое уравнение по диаграмме мура

Дискретная математика

4. Конечные детерминированные автоматы

4.1 Понятие конечного детерминированного автомата

Автоматы можно рассматривать как механизмы, состоящие из:

блока управления, который может пребывать в различных состояниях ( S внутренний алфавит);
входного канала;
выходного канала.

Входной канал считывает входные сигналы ( Х ) из внешней среды. Выходной канал выдает выходные сигналы ( Y ) во внешнюю среду. Работа автомата протекает в дискретные такты времени t =1,2,3,…. По команде в некотором такте времени блок управления установлен в состоянии и входной канал воспринимает , тогда в этом же такте в выходной канал выдается символ , а к следующему такту +1 блок управления перейдет в состояние .

Определение. К.Д.А. называется система , где — алфавит состояний, – входной алфавит, – выходной алфавит. Множества S , X , Y – конечные.

Если в автомате выделено одно состояние , называемое начальным (обычно ), то автомат называется инициальным .

4.2 Способы задания автоматов.

С помощью орграфов. Вершины граф означают состояния, а дуги – переходы между ними. Из каждой вершина исходит k дуг. Из вершины проводится дуга в вершину в том и только в том случае, когда для некоторого .

Этой дуге приписывается пометка :

Начальное состояние в инициальном автомате помечается символом . Описанный таким образом орграф с пометками называется диаграммой Мура.

С помощью канонических уравнений:

в момент t =1 автомат находится в начальном состоянии . В каждый момент t =1,2,3,… дискретного времени автомат, находясь в некотором состоянии s ( t ) из множества S , под действием входного сигнала выдает выходной сигнал из множества Y , согласно функции выходов l , а затем меняет свое состояние на s ( t +1) согласно функции переходов d .

Для определения множества состояний автомата необходимо уяснить содержательный смысл и назначение понятия состояния.

После преобразования входного сигнала в выходной его значение к следующему такту времени теряется. Иначе говоря, в любой тактовый момент t в устройстве нет информации о сигналах в предыдущие моменты, то есть о значениях , , ,… . Поэтому, если при вычислении значения функции переходов и выходов по формуле необходима информация об этих тактовых моментах, то ее нужно каким-либо образом «запомнить». В этом и состоит содержательное назначение состояний. Состояния – это вспомогательные объекты, которые подбираются таким образом, чтобы в совокупности с входным значением однозначно определить выходное значение . Обычно состояния кодируют ту информацию, которая поступила до момента t .

Пример. Построить таблицу переходов–выходов К.Д.А, реализующего функцию:

Чтобы на любом, отличном от первого, такте иметь информацию о , введем два следующих состояния:

И –начальное состояние.

Построим таблицу переходов–выходов:

Для нарисуем диаграмму Мура:

И дополним таблицу переходов–выходов:

4.3 Эквивалентные состояния. Минимизация к.д.а.

Определение. Две диаграммы Мура называются изоморфными , если они могут быть превращены одна в другую переобозначением вершин.

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

Рассмотрим два автомата и с одинаковыми входным и выходным алфавитами.

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

В частном случае, когда = , то речь идет о неотличимых состояниях одного автомата.

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

Неотличимые автоматы осуществляют одно и то же отображение входных слов в выходные.

Определение. Автомат А называется приведенным , если в нем нет эквивалентных (неразличимых) состояний.

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

4.4 Алгоритм минимизации конечного автомата.

Шаг 1 : два состояния s и t относим в один класс , если для любого входного символа x значение функции выхода s совпадает со значениями функции выхода t . В результате получим r классов:

Шаг k : два состояния s и t из одного класса , полученного на предыдущем шаге, относим в один класс , если для любого значения входного символа значения функций состояний принадлежат одному и тому же классу из предыдущего шага. Если шаг k не изменяет разбиения, то процесс останавливается. Доопределяем функции перехода и выхода и строим таблицу переходов –выходов.

Пример. Минимизировать автомат, заданный таблицей:

Шаг 1: Первое, третье и четвертое состояния отнесем в один класс состояний, а второе, пятое и шестое – в другой:

Шаг 2: Выпишем значения функции переходов для состояний из класса :

Видно, что 1 и 3-е состояния относим в один класс этого шага , а четвертое состояние – в другой . Проанализировав аналогичным образом значения функции выходов для состояний из класса , видим:

; ; , т.е. все они остаются в одном классе. В результате получим разбиение на классы:

Шаг 3: ; ; . Дальнейшего разбиения классов не происходит, поэтому процесс останавливается. Класс назовем состоянием , класс состояний назовем состоянием , а класс – состоянием .

Построим таблицу переходов–выходов:

Построенный автомат – минимальный.

4.5 Каноническая таблица. Канонические уравнения.

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

Аргументы функций l и d находятся в столбцах слева, а справа – их значения.

Построить каноническое уравнение по диаграмме мура

Детерминированная функция f(x) называется ограниченно детерминированной (о. д.) функцией, если она имеет конечный вес. Корни поддеревьев каждого типа называют состояниями о. д. функции. (Часто в литературе состоянием называют класс эквивалентности, содержащий все поддеревья одного типа. Содержательно это то же самое.) Таким образом, число различных состояний равно весу функции, а каждое состояние в момент t определяет характер (перспективу) дальнейшего поведения дискретного объекта, математической моделью которого является рассматриваемая о. д. функция.

Пусть о. д. функция f ( x ) имеет r различных состояний. Обозначим их через , где символом помечено начальное состояние, соответствующее корню дерева. Пометим каждую вершину дерева функции f ( x ) одним из символов в зависимости от того, какой тип поддерева эта вершина определяет как корень. Получим дерево, в котором помечены дуги и вершины. Рассмотрим ветвь дерева, исходящую из корня и проходящую через вершины . Для каждой такой ветви произведем усечение ее от вершины, помеченной , если это первая вершина в цепочке , метка которой уже встречалась ярусом выше (возможно в другой ветви). Тогда от каждой ветви в дереве останется лишь начальный отрезок . Полученное дерево назовем усеченным деревом . Если в этом дереве произвести отождествление (стягивание в одну точку)вершин с одинаковыми метками, то получим фигуру (граф), который называется диаграммой Мура . Поскольку при отождествлении вершин нарушается очередность каждой дуги в пучке, то для сохранения этой информации метка y ( t ) каждой дуги дополняется соответствующим значением метки x ( t ) из алфавита X . Таким образом, каждая дуга теперь помечена парой значений ( x ( t ), y ( t )). Вершина, которая являлась корнем в дереве, обычно отмечается дополнительно символом *. Очевидно, что усеченное дерево и диаграмма Мура содержат всю информацию об исходном дереве. Диаграмма Мура – дерево ограниченно детерминированной функции в “свернутом” состоянии.

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

Задание: нарисовать диаграммы Мура для детерминированных функций, рассмотренных в предыдущем параграфе.

Пример 1

Заданная детерминированная функция имеет два состояния, которые обозначим s 0 и s 1
(рис . 1.11).
Тогда начальный фрагмент дерева с помеченными дугами и вершинами имеет вид, как на рис. 1.12.

Применяя правило усечения ветвей, получим усеченное дерево (рис.1.13). Поскольку каждая из концевых вершин уже встречалась ярусом выше, известно, как продолжить дерево до любого яруса t.
Для нахождения диаграммы Мура стягиваем в одну точку все вершины с меткой s 0 , в другую – вершины с метками s 1 , дополняем метки дуг первой координатой, относящейся к соответствующему значению x ( t ) (рис.1.14).

Пример 2

Функция имеет два состояния (рис. 1.15).

Дерево с помеченными дугами и вершинами представлено на рис 1.16, а усеченное дерево на рис. 1.17.

Диаграмма Мура изображена на рис. 1.18.

Если из вершины s i в вершину s j ведет несколько дуг с разными пометками, то можно в диаграмме Мура заменить их одной дугой с несколькими пометками.

Пример 3

У заданной функции 4 состояния (рис. 1.19).

Начальный фрагмент помеченного дерева см. на рис. 1.20. Поскольку метки вершин 3-го яруса уже встречались ярусом выше, то далее дерево можно не продолжать, оно и будет усеченным.

Диаграмма Мура представлена на рис.1.21.

Часто при построении дерева для о. д. функции возникает вопрос: сколько ярусов рисовать в начальном фрагменте дерева? Ответ может быть следующий: рисовать нужно такое количество ярусов, которое позволит на основе формулы и вида дерева определить число состояний функции и изобразить усеченное дерево. Для каждой функции это количество определяется индивидуально.