нет. Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет

• Название: Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет
• Дата: 23.12.2020
• Размер: 0.65 Mb.
• Имя файла: Teoria_avtomatov.docx
• Тип: Учебное пособие; #163524
• страница: 15 из 17

2.6. Модификации конечных автоматов

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

2.6.1. Частичные автоматы

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

Например, это имеется в таблице

Таблица 17

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

В данном случае безразлично состояние автомата начавшего работу из состояния , и считавшего входной символ 0, так же безразличен выход автомата, находящегося в состоянии и считавшего символ 0.

Для представления способа минимизации не полностью описанных автоматов используются следующие определения.

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

Определение 2. Выходная строка покрывает выходную строку (в которой могут быть неопределенные символы), если любой символ из равен соответствующему символу из . Например, строка покрывает строку ; строка 010 покрывает -10, строка 110 покрывает 110 и -10. Если покрывает , то пишут, что .

Определение 3. Если , допустимых для , то говорят, что покрывает , и пишут .

Определение 4. Автомат покрывает , если автомата существует такое состояние автомата , что . Другими словами, каждое состояние автомата покрывается некоторым состоянием автомата . В этом случае пишут

Пример. Имеются два автомата
Автомат М Таблица 18

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

Автомат Таблица 19

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

, Автомат покрывает , т.к. состояния покрывает и , а состояние покрывает .

Заметим, что входная последовательность 01010, считанная автоматом , находящимся в начальном состоянии , перерабатывается в -111-, а считанная в начальном состоянии перерабатывается в 01111. При этом первый безразличный символ на выходе отвечает 0 в , а второй – соответствует 1 в . Таким образом, в ходе работы безразличная позиция в таблице для автомата может заполняться как нулем, так и единицей.

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

Примеры. Строка 01-1 совместима с 0111; строка 0-1- совместима с 011-; но строка 010- несовместима с 011-.

Отметим, что отношение совместимости не является отношением эквивалентности, так как оно рефлексивно, симметрично, но не транзитивно.

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

вероятностного автоматов

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

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

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

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