Конечные автоматы

Задание автомата в виде таблицы и графа

При изображении функций в виде графа: состояния

приписывают вершинам, управления – дугам.

Пример 1. Пусть множество управлений u состоит из управлений α, β, γ, множество состояний x – состояний 1,2,3,4, т.е. u α, β, , x 1,2,3,4 , y 0,1 .

Функции φ (переходов) и (выхода) заданы таблицей

переходов:

x(t)	α
1	2/0
2	2/1
3	3/0
4	2/1

и в виде направленного графа:

u(t)

β
3/1	4/0
-	3/0
4/0	-
1/0	2/1

Конечные автоматы

Задание автомата в виде таблицы и графа

Пример 2. Рассмотрим автомат, который выдает билет при опускании в него монет в сумме 3 руб., причем он принимает монеты 50 коп., 1рубль и 2 рубля. Автомат может давать сдачу.

Требуется составить функцию перехода и выхода.

u α=0,5, β=1, =2 , x 1,2,3,4,5,6 , y 1 0,1 . , y 2 0, 0.5, 1, 1.5

Функция переходов

Функция выхода

Конечные автоматы

Матричное задание автомата

Матрица переходов – квадратная матрица, размерность которой совпадает с числом состояний, а элементами являются дуги, соединяющие состояния

	0			0		0
	0	0			0
		0	0			0
А		0	0	0
		0	0	0	0
		0	0	0	0	0

Минимизация конечных автоматов

Минимизация автоматов – сокращение числа состояний путем объединения эквивалентных состояний.

Состояния называются эквивалентными, если поведение автомата одинаково независимо от того, какое из них является исходным.

Состояние называется k эквивалентным, если автомат, находясь в любом из них, имеет одинаковое поведение в течение k тактов.

k эквивалентные состояния образуют k- эквивалентные классы.

Определение эквивалентных состояний автомата

Автомат представлен в виде графа . Требуется

определить, есть ли у автомата эквивалентные

	состояния.		x	U		u
				x
					α	β
			1
				1,3	1/0	2/1
			2
				2	2/1	1/0
			3	1/0	2/1
						U
			Класс	x		β
			ы	1	1	2
			I
				3	1	2
			II	2	2	1

Аналитическое задание конечных автоматов

Достоинства аналитического представления конечных автоматов:

компактность записи по сравнению с табличным, графовым или матричным заданиями;

простота моделирования работы конечных автоматов на ЭВМ;

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

Для формального описания цифровых управляющих устройств применяется аппарат алгебры логики.

Основная функционально полная система

Включает операции &, и инверсию

x	y	x & y	x y	инв x	инв y
0	0	0	0	1	1
0	1	0	1	1	0
1	0	0	1	0	1
1	1	1	1	0	0

Хаггарти Р. Дискретная математика для программистов. М.: Техностфера, 2012 – 400 с.

Нормальные формы

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа различных членов, каждый из которых представляет собой конъюнкцию отдельных переменных или их отрицаний, входящих в данный набор не более одного раза (xyz) (xz) ( yz)

Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа различных членов, каждый из которых представляет собой дизъюнкцию отдельных переменных или их отрицаний, входящих в данный набор не более

одного раза		(x	y z)(x	z)( y	z)
СДНФ –	xyz		СКНФ –	(x	y)(x y)
		xyz xyz

Разложение функций на конституенты

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

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

Переход от табличного задания функции к аналитическому

Табличное представление функции

	a	b	c	Функция в виде СДНФ:
				f
	0	0	0	1
					fСДНФ a b c							a b c
	0	0	1	0
	0	1	0	1
	0	1	1	1
				Функция в виде СКНФ:
	1	0	0	0
	1	0	1	1
					fСКНФ a					b		c a
	1	1	0	0
	1	1	1	1

a bc abc abc

b c a b c