Page 34 - 4128

Z W
S

Рисунок 2.1 - Абстрактний автомат

Абстрактний автомат (рис.2.1) має один вхід і один
вихід. Автомат працює в дискретному часі, що набуває цілих
додатних значень 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. Тобто якщо на
вхід автомата, встановленого в початковий стан a 1, подавати
буква за буквою деяку послідовність букв вхідного алфавіту
z(0), z(1),... - вхідне слово, то на виході автомата послідовно
з'являтимуться букви вихідного алфавіту w(0), w(1),... -
вихідне слово. Тобто, вихідне слово = (вхідне слово), де  -
відображення, здійснюване абстрактним автоматом.
На рівні абстрактної теорії поняття "робота автомата"
розуміється як перетворення вхідних слів у вихідні. Можна
сказати, що в абстрактному автоматі абстрагуються від його
структури - вмісту “чорної скриньки” (рис. 14), тобто основну
увагу надаємо поведінці автомата щодо зовнішнього
середовища.
Поняття стану у визначенні автомата введене у зв'язку
з тим, що часто виникає необхідність опису поведінки систем,
виходи яких залежать не тільки від стану входів в даний
момент часу, але і від деякої передісторії, тобто від сигналів,
які поступали на входи системи раніше. Стани якраз і
відповідають деякій пам'яті про минуле, дозволяючи усунути
33