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

Дискретный автомат – модель дискретного устройства, отражающего свойство обработки

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

Состояния входов: X = {x₁, x₂, x₃… x_n};

Состояние выходов: Y = {y1, y2, y3… yn};

Внутренние состояния: S = {s₁, s₂, s₃… s_n};

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

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

Различают автоматы:

· Комбинационные, состояние выходов определяется состоянием входов (шифрато-

ры, мультиплексоры) y_j = 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

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

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

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

ренние состояния и какие сигналы должны быть при этом на выходах