Определение абстрактного автомата.

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

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

Проще говоря, эвристика это не полностью математически обоснованный (или даже «не совсем корректный»), но при этом практически полезный алгоритм.

Важно понимать, что эвристика, в отличие от корректного алгоритма решения задачи, обладает следующими особенностями:

· Она не гарантирует нахождение лучшего решения.

· Она не гарантирует нахождение решения, даже если оно заведомо существует (возможен «пропуск цели»).

· Она может дать неверное решение в некоторых случаях.

 

 

Тема: Задание и функционирование абстрактных автоматов

Цель работы:

· Изучить способы задания абстрактных автоматов.

· Изучить способы функционирования абстрактных автоматов

Задание

Автомат Мили

δ a1 a2 a3 a4 z1 a1 a4 a1 a2 z2 a2 a3 a3 a3

λ a1 a2 a3 a4 z1 w1 w1 w3 w1 z2 w2 w3 w2 w2

 

a1

a2

a3

a4

z1

z1

z1

z1

z2

z2

z2

z2

w3

w1

w1

w1

w2

w2

w2

w3

Подадим в автомат входное слово

ξ	z2	z1	z1	z1	z2	z2	z1	z1	z2	z2
	a1	a2	a4	a2	a4	a3	a3	a1	a1	a2	a3
ω	w2	w1	w1	w1	w2	w2	w3	w1	w2	w3

 

 

Автомат Мура

	w1	w1	w3	w2
a1	a2	a3	a4
z1	a1	a4	a1	a2
z2	a2	a3	a3	a3

 

a1

a2

a3

a4

z1

z1

z1

z1

z2

z2

z2

z2

w1

w2

w1

w3

Подадим в автомат входное слово

ξ	z2	z1	z1	z1	z2	z2	z1	z1	z2	z2
	a1	a2	a4	a2	a4	a3	a3	a1	a1	a2	a3
ω		w1	w2	w1	w2	w3	w3	w1	w1	w1	w3

 

Контрольные вопросы

Определение абстрактного автомата.

Абстрактный автомат- математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного алфавита, на выходе оно выдаёт символы (в общем случае) другого алфавита.

Формально абстрактный автомат определяется как пятерка

Где S — конечное множество состояний автомата, X, Y — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом, — функция переходов, — функция выходов.

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

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

Ограничение числа параметров абстрактного автомата определило такое понятие как конечный автомат.

Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата и последовательности выходных символов , которые для последовательности символов разворачиваются в моменты дискретного времени t = 1, 2, 3, … Моменты дискретного времени получили название тактов.

Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений:

Примеры реальных конечных автоматов.

Представим, что в текстовой строке вам нужно распознать последовательность символов «//». На рисунке 1 показано, как это выполняется при помощи конечного автомата. Первое появление слеша не дает выходного сигнала, но приводит к тому, что автомат переходит во второе состояние. Если во втором состоянии автомат не находит слеша, он возвращается к первому, поскольку необходимо наличие 2-х слешей подряд. Если второй слеш найден, автомат выдает сигнал «готово».