лекции ВТиИТ / 04_Элементы теории автоматов

Теория автоматов

Дискретный автомат – модель дискретного устройства, отражающего свойство обработки информации этим устройством. Для описания используют множество значений сигналов. Состояния входов: X = {x1, x2, x3… xn};

Состояние выходов: Y = {y1, y2, y3… yn}; Внутренние состояния: S = {s1, s2, s3… sn};

В общем случае состояние выхода yj = f[X(t); S(t)]

Если выход зависит только внутреннего состояния, то собственный выход yсобств = f[S(t)] Различают автоматы:

Комбинационные, состояние выходов определяется состоянием входов (шифраторы, мультиплексоры) yj = f[X(t)].

Автоматы с памятью (присутствуют ячейки памяти), состояние автомата определяется {X,S}, при этом состояние может быть устойчивым (не изменятся до изменения входного сигнала) и неустойчивым (т. е. стремится перейти в новое состояние (мультивибратор)).

Конечные – автоматы, задаваемые конечным набором входных и выходных сигналов и конечным множеством внутренних состояний, при этом переходы из одного состояния в другое считаются мгновенными (переходных процессов нет).

Среди конечных автоматов разделяют синхронные и асинхронные.

Автомат Мили: S(t+1) = f[S(t); X(t)]; Y(t) = f[S(t), X(t)] Автомат Мура: S(t+1) = f[S(t); X(t)]; Y(t) = f[S(t)]

Если учитываем время перехода из состояния в состояние (переходный процесс) – динамический автомат.

Вероятностный автомат – поведение не детерминировано (переходы неоднозначны)

S(t) = f[S(t-1)X(t),λ(X,S)]

λ(X,S) – вероятностная характеристика.

Способы задания функции работы автомата:

Табличный (таблицы истинности)

Xi Si Sj Y

Таблица содержит 2n строк – по числу наборов значений аргументов, и n столбцов – число аргументов и один столбец значения функции.

В каждой строке таблицы записывают, какие сигналы должны быть на входе, какие внутренние состояния и какие сигналы должны быть при этом на выходах

S3

Типы реализации автоматов

На элементах с жесткой логикой

Автомат Мура:

C

Автомат Мили:

Реализуются в качестве программ для процессоров и микроконтроллеров.