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

Поняття абстрактного автомата використовується для опису процесу функціонування дискретних систем. Абстрактний автомат є математичною моделлю функціонування дискретних пристроїв (ДУ).

Поводження будь-якого ДУ визначається зміною його вхідних і вихідних символів і внутрішніх станів. Особливістю функціонування ДУ є те, що в часі можуть бути виділені інтервали, протягом яких змінні зберігають постійне значення і які називають тактами роботи ДУ.

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

A = (X, Y, S, d, l, {s₀})

де X = {x₁, x₂,..., x_m} - вхідний алфавіт (множина вхідних сигналів),
Y = {y_1,y_2,..., y_h} – вихідний алфавіт (множина вихідних сигналів),
S= {s₁, s_2...,s_n} - алфавіт внутрішніх станів (множина внутрішніх станів), d:X´S®S – функція переходів, що ставить у відповідність парам <s_i,x_j> внутрішній стан з S, s_k=d(s_i,x_j), l:X´S®Y - функція виходів, що ставить у відповідність парам <s_i,x_j> вихідний сигнал з U, y_h=l(s_i,x_j), s₀- початковий стан автомата з множині S.

У кожен момент дискретного часу t абстрактний автомат знаходиться в деякому внутрішньому стані s(t), причому s₀= s(0).

Автомат у момент t здатний сприйняти на вході букву вхідного алфавіту x(t). Відповідно до функції виходів автомат видасть у той же момент часу t вихідний сигнал у(t) – букву вихідного алфавіту, а до наступного моменту часу (t +1) перейде у новий стан s(t+1), що обумовлений функцією переходів.

Автомат реалізує відображення множини слів вхідного алфавіту X у множину слів вихідного алфавіту Y. Якщо на вхід автомата подати послідовність букв вхідного алфавіту <x(0), x(1), x(2), x(3),...>, то на виході автомата будуть з'являтися букви вихідного алфавіту <y (0), y(1), y(2), y(3),...> - вихідне слово. Робота автомата зводиться до перетворення вхідних слів у вихідні.

Логічна чи комбінаційна схема (КС) є окремним випадком автомата, в якому вихідні сигнали не залежать від внутрішніх станів автомата, тобто множина S має один стан s₀.

A = (X, Y, l),

l = X®Y

Якщо функції d і l визначені на всій множині пар з S´X, то автомат називається скрізь визначеним, інакше – автомат називається частковим. Автомат називається скінченним, якщо скінченними є множини S, X, Y.

У практиці найбільше поширення одержали автомати Мілі і Мура.