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

Абстрактний автоматтеорії алгоритмів) - математична абстракція, модель дискретного пристрою, що має один вхід, один вихід і в кожний момент часу знаходиться в одному стані з безлічі можливих. На вхід цього пристрою надходять символи одного алфавіту, на виході воно видає символи (в загальному випадку) іншого алфавіту.

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

Формально абстрактний автомат визначається як п'ятірка

\ 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)).}

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

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

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