Математичною моделлю ЦА (а в загальному випадку будь-якого дискретного пристрою) є так званий абстрактний автомат, визначений як 6-компонентний кортеж: S=(A,Z,W,,,а1) у якого:

A={a1, a2, ...,am} – безліч станів (внутрішній алфавіт);

Z={z1, z2, ...,zf} – безліч вхідних сигналів (вхідний алфавіт);

W={w1, w2, ..., wg} – безліч вихідних сигналів (вихідний алфавіт);

– функція переходів, що реалізує відображення . Іншими словами функція деяким парам стан – вхідний сигнал (аm, zf) ставить у відповідність стани автомата аs= (am, zf), asА.

– функція виходів, що реалізує відображення . Функція деяким парам стан – вхідний сигнал (аm, zf) ставить у відповідність вихідні сигнали автомата Wg=(аm, zf), WgW.

ai А – початковий стан автомата.

Під алфавітом тут розуміється непорожня множина безліч попарно різних символів. Елементи алфавіту називаються буквами, а кінцева впорядкована послідовність букв - словом в даному алфавіті.

Рисунок 1.2 – Абстрактний автомат

Абстрактний автомат (рис.1.2) має один вхід і один вихід. Автомат працює в дискретному часі, що приймає цілі додатні значення t = 0,1,2,... У кожний момент t дискретного часу автомат знаходиться в деякому стані а(t) - одному з безлічі станів автомата, причому в початковий момент t = 0 він завжди знаходиться в початковому стані а(0)=a1. У момент t, будучи в стані а(t), автомат здатний сприйняти на вході букву вхідного алфавіту z(t) Z. Відповідно до функції виходів він видасть в той же момент часу t букву вихідного алфавіту W(t)=(а(t), z(t)) і відповідно до функції переходів перейде в наступний стан а(t+1)=[а(t), z(t)], а(t) А, w(t) W.

Значення поняття абстрактного автомата полягає у тому, що він реалізує деяке відображення безлічі слів вхідного алфавіту Z в безліч слів вихідного алфавіту W. Тобто якщо на вхід автомата, встановленого в початковий стан a1, подавати буква за буквою деяку послідовність букв вхідного алфавіту z(0), z(1),... - вхідне слово, то на виході автомата послідовно з'являтимуться букви вихідного алфавіту w(0), w(1),... - вихідне слово. Тобто, вихідне слово = (вхідне слово), де - відображення, здійснюване абстрактним автоматом.

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

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

На практиці найбільше поширення набули два класи автоматів - автомати Мілі (Mealy) і Мура (Moore).

Закон функціонування автомата Мілі задається рівняннями:

а(t+1)= (а(t), z(t)); w(t)= (а(t), z(t)), t = 0,1,2,...

Закон функціонування автомата Мура задається рівняннями:

а(t+1)=(а(t), z(t)); w(t)= (а(t)), t = 0,1,2,...

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

Окрім автоматів Мілі і Мура іноді виявляється зручним користуватися суміщеною моделлю автомата, так званим С-автоматом.

Під абстрактним С-автоматом розуміється математичну модель дискретного пристрою, що визначається восьмикомпонентним вектором S=(А, Z, W, U, , 1, 2, а1), у якого:

1. A={a1, a2, ...,am} – безліч станів;

2. Z={z1, z2, ...,zf} – вхідний алфавіт;

3. W={w1, w2, ..., wg} – вихідний алфавіт типу 1;

4. U={u1, u2,...,uh} – вихідний алфавіт типу 2;

5. – функція переходів, яка реалізує відображення ;

6. – функція виходів, яка реалізує відображення ;

7. – функція виходів, яка реалізує відображення ;

8. а1 А – початковий стан автомата.

Розглянуті вище абстрактні автомати можна розділити на:

Повністю визначеним називається абстрактний цифровий автомат, у якого функція переходів і функція виходів визначені для всіх пар (ai, zj).

Частковим називається абстрактний автомат, у якого функція переходів або функція виходів, або обидві ці функції визначені не для всіх пар (ai, zj).

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

Інакше це буде автомат ймовірності, в якому при заданому стані ai і заданому вхідному сигналі zj можливий перехід із заданою вірогідністю в різні стани.

Для визначення синхронних і асинхронних автоматів вводиться поняття стійкого стану. Стан as автомата називається стійким, якщо для будь-якого стану ai і вхідного сигналу zj таких, що (ai, zj) = as має місце (as, zj) = as, тобто стан стійкий, якщо потрапивши в цей стан під дією деякого сигналу zj, автомат вийде з нього тільки під дією іншого сигналу zk, відмінного від zj.

Автомат, у якого всі стани стійкі - асинхронний.

Автомат називається синхронним, якщо він не є асинхронним.

Абстрактний автомат називається кінцевим, якщо кінцеві множини А = {a1, a2, ..., am}, Z = {z1, z2, ..., zf}, W = {w1, w2, ..., wg}. Автомат носить назву