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

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

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

, i = 1, 2, …, k.

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

Пример 1.

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

Пример 2.

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

Пример 3.

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

.

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

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

Type

Prep = record

Number: Integer;

Stroka: String;

Zn: Boolean;

End;

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

Function otr (a: prep; var b: 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 с.: ил.