Дискретная математика (стр. 10 из 10)

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

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

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

Рассмотрим модели, которые представлены в виде некоторого черного ящика, на вход которого поступают некоторые логические переменные x₁, x₂,…, x_n. Объект их перерабатывает, и на выходе получаем некоторые логические функции y₁, y₂,…, y_k.

Рис. 8. Логический конечный автомат

Такие модели называют логически конечными автоматами. Существуют некоторые классы таких автоматов:

- автоматы без памяти (комбинационные)

- автоматы с памятью (последовательностные).

3.12.2.1 Конечные автоматы без памяти (комбинационные)

Общая формула, описывающая этот вид автоматов:

, i = 1, 2, …, k.

– в векторной форме

Пример 1.

Примером таких автоматов является простая экспертная система профессиональной пригодности, где входные значения – это ответы на n вопросов, а выходные – k выводов о том, может ли человек работать в данной области.

Пример 2.

Диагностика неисправностей, заболеваний и т. д.

Пример 3.

Пусть функционирование логического автомата описывается формулой:

.

На языке Pascal оператор присваивания, соответствующий этой формуле:

Для более сложной модели получается структура типа запись:

Type

Prep = record

Number: Integer;

Stroka: String;

Zn: Boolean;

End;

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

Functionotr (a: prep; varb: prep; параметры сохранения и т. д.): Boolean;

Function con (a, b: prep; var c: prep; параметрысохраненияи т. д.): Boolean;

Function diz (a, b: prep; var c: prep; параметрысохраненияи т. д.): Boolean;

Пример 4.

Отмоделировать функцию Y_i:

Высказываниемоделируетсязаписью:

Function y1 (x₁, x₂, x₃, x_4: prep; var rez: prep; sohr: Boolean; newnumber: Integer; t: String): Boolean;

Var

I: boolean; a, b, c, d, e,: prep;

Begin

I:= otr(x₁, a, false, 0);

I:= otr(x₂, b, false, 0);

I:= con (a, b, c, false, 0);

I:= con (c, x₃, d, false, 0);

I:= otr(x₃, a, false, 0);

I:= otr(x₄, a, false, 0);

I:= con(x₂, a, c, false, 0);

I:= con (c, b, e, false, 0);

I:= diz (d, e, rez, false, 0);

If sohr then begin

rez.number:=newnumber;

rez.stroka:=t;

end;

y1:=rez.znachenie;

end;

Отмоделировать функцию лучше программным путем, т. к. программу довольно просто модифицировать.

3.12.2.2 Конечные автоматы с памятью (последовательностные)

Для таких автоматов характерно наличие вектора внутренних состояний z=(z₁, z₂,…, z_m).

В таких автоматах каждая логическая функция зависит от входных функций x и функций внутреннего состояния z.

Рис. 10. Конечный автомат с памятью

. (8)

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

определяется выражением (8). В момент времени t₁=t₀+tвходной вектор может поменяться, в свою очередь может поменяться вектор состояний Y.

, (9)

где t– такт логического конечного автомата. Считается, что t много больше времени расчета на ЭВМ.

Пример.

Та же самая экспертная система определения профессиональной пригодности, но с условием, что значение о профессиональной пригодности зависит от ранее полученных ответов. Такие экспертные системы называют самообучающимися, т. к. сразу правильного ответа не дают. Частным случаем конечного автомата с памятью является автомат с обратной связью по выходу. Для него вектор внутренних состояний в момент времени t+t равен вектору выходных сообщений в момент времени t. Пример конечного автомата с памятью и обратной связью по выходу приведен на рис. 11.

Рис. 11. Конечный автомат с памятью и обратной связью по выходу

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

Const

N=…; k=…;

Type

Vector x = array [1..n] of boolean;

Vector y = array [1..k] of boolean;

Var

X: vector X;

Ypred, Y: vector Y;

Procedure tact (v: vector X; var Ypred, Y: vector Y);

Var

I: integer;

Begin

Y[1]:=y₁(…);

Y[2]:=y₂(…);

Y[3]:=y₃(…);

Y[k]:=y_k(…);

For i:=1 to k do

Ypred[i]:= Y[i];

End;

End.

Состояние конечного автомата называется установившимся, если с течением времени при постоянном значении входного вектора Х, вектор Y принимает постоянное значение. В этом случае процесс обучения конечного автомата заканчивается, и результаты его работы могут быть использованы. Однако существуют автоматы, состояние которых не устанавливается с течением времени. Такие автоматы используются только в схемотехнике. Примером такого автомата является автомат триггерного типа. Логическая схема триггера приведена на рис. 12.

Рис. 12. Автомат триггерного типа

Другим частным случаем является автономный конечный автомат, для которого вектор входных воздействий

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

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

1. Что такое логический конечный автомат?

2. Представьте в виде рисунка логический конечный автомат.

3. Что такое такт конечного логического автомата?

4. Приведите пример конечного автомата без памяти.

5. Приведите пример конечного автомата с памятью.

6. Приведите пример конечного автомата с обратной связью по выходу.

Библиографический список

1. Акимов В.А. Дискретная математика: логика, группы, графы. М.: Лаборатория Базовых Знаний, 2003, 376 с.

2. Стол Роберт Р. Множества. Логика. Аксиоматические теории. Пер. с англ. Ю.А. Гастева И.Х. Шмаина. Под ред. Ю.А. Шихановича. М., «Просвещение», 1968, 232 с.

3. Ершов Ю.А., Полюнин Е.А. Математическая логика: Учебное пособие для вузов. М.: Наука. Гл. ред. физ. – мат. лит., 1987, 336 с.

4. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Высшая школа, 2003, 256 с.

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

6. Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: Учебное пособие. – М.: ФОРУМ: ИНФРА-М, 2004, 128 с.

7. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2003, 280 с. – (Серия «Высшее образование»)

8. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2001, 304 с.: ил.