2.6.2. Понятия недетерминированного и вероятностного автомата

Недетерминированный автомат – это такой, который при данном входном символе и определенном состоянии может переходить в несколько различных внутренних состояний. Формально недетерминированный автомат это пятерка такие что отображение - не является однозначным. Справедливо утверждение. Если недетерминированный автомат является конечным, то существует алгоритм, позволяющий построить конечный автомат, эквивалентный исходному автомату. При этом недетерминированный автомат имеет больше состояний, чем исходный недетерминированный автомат.

Вероятностный автоматпредставляет собой набор , где- конечные множества ,- функция, определенная на множестве и принимающая в качестве своих значений вероятностные меры на множестве . - функция, определенная на и принимающая в качестве своих значений вероятностные меры на множестве . Т.к.SиBконечны, то соответствующие вероятностные меры задаются векторамии

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

Аналогично, для задания использована система стохастических матриц размерности . , где - вероятность появления на входе символа , если автомат находится в состоянии ви на его вход поступает .

2.7. Процедура минимизации не полностью описанного автомата

2.7.1. Совместимые состояния

Определение.Состояниеназывается совместимым по выходу с состоянием, если. В этом случае пишется .Если состояния не совместимы по выходу, то пишут

Напримердля автомата

Текущее состояние	Следующее состояние		Выход
	0	1	0	1
			0	1
			-	1
			1	1

, т.е. отношениене транзитивно

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

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

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

2.7.2. Техника определения совместимых состояний.

Пусть требуется определить отношения совместимости состояний для не полностью описанного автомата, заданного таблицей состояний.

Текущее состояние	Следующее состояние				Выход
		-			0	-	-	-
				-	0	1	0	-
			-		0	1	-	0
	-			-	-	1	-	-
	-	-		-	-	-	1	-

Сначала следует определить т.к. оно является подмножеством.содержит одну пару (2,5). Все остальные пары

Составим таблицу совместимости, строки которой нумеруются элементами , а столбцы входными символами

(1,2)	(2,3)	-	(2,3)	-
(1,3)	(2,3)	-	-	(2,5)
(1,4)	-	-	(2,3)	-
(1,5)	-	-	(1,3)	-
(2,3)	-	(4,5)	-	-
(2,4)	-	(1,5)	-	-
(3,4)	-	(1,4)	-	-
(3,5)	-	-	-	-
(4,5)	-	-	(1,2)	-

На пересечении столбцы и строкиуказаны пары состояний, в которыепереводит пару. Например, переводитвив; Поэтому на пересечении (1,2) истоит (2,3). Если одно или оба из следующих состояний безразличны, или исходная пара переходит в одно и то же состояние, то в соответствующей позиции ставится прочерк.

Предположим, что некоторый элемент множества переводится в элемент множества некоторой входной строкой. Тогда первоначальный элемент лежит в. Следовательно после применения этого входа для получившийся пары изполучаются разные выходы, и следовательно будут выходы для первоначальной пары. Например,переводит (1,3) в (2,5), а (2,5), т.к. эти состояния 2 и 5 дают разные выходы при входе. Поэтому состояния (1,3) дадут разные выходы при входе. Далее составляем список элементов множества.(т.к. отношение совместимости рефлексивно и симметрично, то выписываются пары

Затем добавляются пары, которые некоторым символом переводятся в только что полученные пары. Эти пары различаются подходящим входом длины 3. В нашем случае на этом шаге добавляется пары (1,5) и т.д. В результате график отношений имеет вид:

Процедуры заканчиваются тогда, когда новые пары перестают возникать. Это произойдет не позже чем через шагов, гдечисло состояний автоматы. Последнее полученное отношение будет.остальыне пары