Детерминированная функция 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.
Часто при построении дерева для о. д. функции возникает вопрос: сколько ярусов рисовать в начальном фрагменте дерева? Ответ может быть следующий: рисовать нужно такое количество ярусов, которое позволит на основе формулы и вида дерева определить число состояний функции и изобразить усеченное дерево. Для каждой функции это количество определяется индивидуально.
Пример 4
Состояния о. д. функции: 
Помеченное, усеченное деревья и диаграмма Мура представлены соответственно на рис. 1.22, 1.23, 1.24.
Чтобы не загромождать рисунок, двоичную пару, соответствующую очередности дуги, записывают без скобок и запятой между координатами.
Пример 5
Состояния имеют вид:
Усеченное дерево и диаграмма Мура изображены на рис. 1.25, 1.26.
Построить диаграмму мура каноническую таблицу и канонические уравнения для функции
Видео:Как строить автомат: диаграмма МураСкачать
Дискретная математика
4. Конечные детерминированные автоматы
4.1 Понятие конечного детерминированного автомата
Автоматы можно рассматривать как механизмы, состоящие из:
- блока управления, который может пребывать в различных состояниях ( S внутренний алфавит);
- входного канала;
- выходного канала.
Входной канал считывает входные сигналы ( Х ) из внешней среды. Выходной канал выдает выходные сигналы ( Y ) во внешнюю среду. Работа автомата протекает в дискретные такты времени t =1,2,3,…. По команде в некотором такте времени блок управления установлен в состоянии и входной канал воспринимает , тогда в этом же такте в выходной канал выдается символ , а к следующему такту +1 блок управления перейдет в состояние .
Определение. К.Д.А. называется система , где — алфавит состояний, – входной алфавит, – выходной алфавит. Множества S , X , Y – конечные.
Если в автомате выделено одно состояние , называемое начальным (обычно ), то автомат называется инициальным .
4.2 Способы задания автоматов.
Таблица переходов–выходов.
