Page 33 - 4128

2. ОСНОВНІ ПОНЯТТЯ І ВИЗНАЧЕННЯ ТЕОРІЇ
АБСТРАКТНИХ АВТОМАТІВ

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

програмне управління.
Цифровий автомат - пристрій, що характеризується
набором внутрішніх станів, в які він переходить під впливом
команд закладеної в нього програми. Перехід автомата з
одного стану в інший здійснюється в певний момент часу.
Математичною моделлю ЦА (а в загальному випадку
будь-якого дискретного пристрою) є так званий абстрактний
автомат, визначений як 6-компонентний кортеж:
S=(A,Z,W,,,а1) у якого:
1. A={a1, a2, ...,am} - безліч станів (внутрішній
алфавіт);
2. Z={z1, z2, ...,zf} - безліч вхідних сигналів (вхідний
алфавіт);
3. W={w1, w2, ..., wg} - безліч вихідних сигналів
(вихідний алфавіт);
4.  : АZА - функція переходів, що реалізує
відображення D  АZ в А. Іншими словами функція 
деяким парам стан - вхідний сигнал (а m, z f) ставить у
відповідність стани автомата а s=  (a m, z f), a sА.
5.  : АZW - функція виходів, що реалізує
відображення D  АZ на W. Функція  деяким парам стан -
вхідний сигнал (а m, z f) ставить у відповідність вихідні сигнали
автомата Wg=(а m, zf), W gW.
6. a i А - початковий стан автомата.
Під алфавітом тут розуміється непорожня множина
безліч попарно різних символів. Елементи алфавіту
називаються буквами, а кінцева впорядкована послідовність
букв - словом в даному алфавіті.

32