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

Видеокарта

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

Видеокарта компании Gigabyte

Основные компоненты видеокарты это графический процессор, видеоконтроллер, видеопамять и цифро-аналоговый преобразователь.

Определение:

Абстрактный автомат - это модель преобразователя (устройства), которая характеризуется алфавитом входа, алфавитом выхода, алфавитом состояний, функцией выхода, функцией перехода:
S=<Z,W,A,l,d>
где
Z = {z₁,z₂,...,z_m}- алфавит входа,
W = {w₁,w₂,...,w_n} - алфавит выхода,
A = {a₁,a₂,...,a_p} - алфавит состояний,
l: A x Z -> W - функция выхода,
d: A x Z -> A - функция перехода

Предполагается, что автомат находиться всегда в некотором состоянии, и если это состояние a_i, то функция l определяет, какой выход будет иметь преобразователь, а d - какое у него будет новое состояние, если значение входа автомата равно w_j.

Под алфавитом здесь понимается непустое множество попарно различных символов.

Способы задания автомата

Чтобы задать конечный автомат S, необходимо описать все компоненты вектора S=<Z,W,A,l,d>, то есть входной и выходной алфавиты состояний, а также функции переходов и выходов.Среди множества состояний необходимо выделить состояние a₁, в котором автомат находится в момент времени t=0.

Существуют несколько способов задания автомата, но наиболее часто используются табличный и графический.

1. Описание работы автомата таблицами переходов и выходов иллюстрируется на следующем примере:

Функция перехода d: A x Z -> A

Функция выхода l: A x Z -> W

Строки этих таблиц соответствуют входным сигналам, а столбцы - состояниям, причем крайний левый столбец обозначен начальным состоянием a₁. На пересечении столбца i и строки j в таблице переходов ставится состояние (i,z_j)=a_s, в которое автомат переходит из состояния a_i под действием сигнала z_j,а в таблице выхода - соответствующий этому переходу выходной сигнал w(i,j)=l(a_i,z_j)=w_r.

1. Для описания работы автомата можно использовать объединенную таблицу:

Функции перехода и выхода

a(i,j)=d(a_i,z_j)=a_s; w(i,j)=l(a_i,z_j)=w_r

1. Определение: Граф автомата - ориентированный граф, вершины крторого соответствуют состояниям, а дуги - переходам между ними, например: