Абстрактний автомат — це алгоритмічна система, яку визначають три множини: вхідний алфавіт Х, вихідний алфавіт У, множина внутрішніх станів автомата S, а також дві функції (функція переходів та функція виходів). Щоб задати абстрактний автомат, є такі способи: функціональний, за допомогою таблиць переходів та виходів і графічний (залежно від способу задання функцій).
Функціональний спосіб задання абстрактних автоматів.
Автомат працює у дискретному часі. Послідовні моменти часу ототожнюють із послідовними натуральними числами t = 0, 1, 2 ... (це завжди можна зробити, обравши за одиницю часу будь-який зручний відрізок виміру).
У кожний момент автоматного часу t = 0, 1, 2 ... автомат А знаходиться у деякому стані S(t) Î S. Початковий стан автомата А — S(0).
У кожний момент часу t, починаючи з t = 1, до входу автомата надходить одна літера x(t) Î X вхідного алфавіту (вхідний сигнал). Вхідними словами автомата будуть скінченні впорядковані послідовності вхідних сигналів x(1) x(2) ... x(k). Кожний автомат має множину припустимих вхідних слів. Будь-яке припустиме слово p = x(1) x(2)... x(k), що подане до входу автомата, викликає появу вихідного слова q = y(1)y(2) ... y(k) — впорядкованої послідовності вихідних сигналів автомата А тієї самої довжини.
Відповідність між припустимими вхідними словами p і вихідними словами q називають алфавітним відображенням, індукованим автоматом А. Це відображення однозначно задається двома функціями — функцією переходів з одного стану в інший та функцією виходів, що визначає вихідний символ або сигнал.
Стан автомата S(t) у будь-який момент часу t однозначно визначається попереднім станом S(t-1) та вхідним сигналом x(t). Але щодо моменту часу t переходу зі стану S(t-1) у стан S(t), вихідний сигнал y(t) може з’явитися або до переходу, або після нього. Тому y(t) може бути визначений двома способами:
Функція Y є функцією виходів. Причому Y * — це звичайна функція, яка визначає вихідну літеру y(t) залежно від вхідного сигналу x(t) в момент t та від стану y попередній момент часу S(t–1), Y** — функція зсунута, яка визначає вихідну літеру y(t) залежно від стану s(t) в момент часу t і вхідного сигналу x(t) в той самий момент часу t.
Залежно від визначення y(t) розрізняють два типи абстрактних автоматів:
— це автомат I роду, або автомат Мілі,
— це автомат II роду, або автомат Мура.
Якщо всі три множини X, Y, S, що визначають абстрактний автомат А, є скінченними, то й автомат називають скінченним.
