Абстрактный автомат

Абстра́ктный автома́ттеории алгоритмов) — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного языка, на выходе оно выдаёт символы (в общем случае) другого языка.

Формально абстрактный автомат определяется как пятерка

\boldsymbol{A = (S, X , Y, \delta , \lambda)}

Где S — конечное множество состояний автомата, X, Y — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом, \delta : S \times X \rightarrow S — функция переходов, \lambda : S \times X \rightarrow Y — функция выходов.

Абстракный автомат с выделенным начальным состоянием называется инициальным автоматом. Таким образом, абстрактный автомат определяет семейство инициальных автоматов

\boldsymbol{(s_i, A), s_i \in S}

Если функции переходов и выходов однозначно определены для каждой пары \boldsymbol{(s, x) \in S \times X}, то автомат называют детерминированным. В противном случае автомат называют недетерминированным или частично определенным.

Если функция переходов и/или функция выходов являются случайными, то автомат называют вероятностным.

Ограничение числа параметров абстрактного автомата определило такое понятие как конечный автомат.

Функционирование автомата состоит в порождении двух последовательностей: последовательности очередных состояний автомата \boldsymbol{s_1[1]s_2[2]s_3[3]...} и последовательности выходных символов \boldsymbol{y_1[1]y_2[2]y_3[3]...}, которые для последовательности символов \boldsymbol{x_1[1]x_2[2]x_3[3]...} разворачиваются в моменты дискретного времени t = 1, 2, 3, … Моменты дискретного времени получили название тактов.

Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений: \boldsymbol{s(t+1)=\delta(s(t),x(t));}

\boldsymbol{y(t)=\lambda(s(t),x(t)).}

Для уточнения свойств абстрактных автоматов введена классификация.

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

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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home