Поняття автомата. Види автоматів

В технічних (технологічних) системах автоматами називають пристрої, за допомогою яких здійснюються операції прийому, перетворення і передачі матеріальних об’єктів або інформації у відповідності з певною програмою, без безпосередньої участі людини. Задачі синтезу та аналізу технологічних автоматів, що здійснюють операції прийому, перетворення і передачі матеріальних об’єктів, відносяться до галузі машинобудування.

За функціональним призначенням автомати, що застосовуються в системах керування, діляться на три види: інформаційні, керуючі та обчислювальні. До інформаційних автоматів відносяться різноманітні довідкові таблиці, наприклад, на вокзалах, інформаційні табло на стадіонах, різні пристрої аварійної сигнализації. До керуючих автоматів прийнято відносити пристрої для керування технічними об’єктами шляхом формування команд керування в дискретній формі. До обчислювальних автоматів відносять ЕОМ, мікроконтролери. Однак всі ці автомати по суті є одночасно обчислювальними, керуючими та інформаційними за сукупністю процесів, що в них здійснюються. Такі автомати є основою сучасної обчислювальної техніки та систем автоматичного контролю і управління.

Під терміном “автомат” в дискретному аналізі розуміють абстрактну модель пристрою (абстрактний автомат), що функціонує в дискретному часі, переробляючи потоки вхідних сигналів в потоки вихідних сигналів. На мові теорії множин це означає, що абстрактный автомат відображає множину вхідних сигналів у множину вихідних сигналів. В абстрактному автоматі вхідні та вихідні сигнали мають вид послідовностей символів, тобто слів у відповідних (вхідному, вихідному) алфавітах. В процесі роботи автомата здійснюється послідовна зміна його станів в дискретні моменти часу під впливом вхідних сигналів.

Згадана тут дискретизація реального часу базується на понятті автоматного часу. Шкала дискретного часу зображена на рис. 4.1. На осі часу цілими числами 0, 1, 2, ..., i позначені моменти часу , в які вхідні і вихідні сигнали автомата можуть змінювати своє значення. Зазначені моменти часу називаються тактами.

Рисунок 4.1 – Шкала дискретного часу: i – номер такта

Тривалість Dt імпульсів напруги в сучасних дискретних пристроях автоматики вимірюється мікросекундами і наносекундами. За фіксований інтервал часу Dt=t_і+1–t_і (рис. 4.1) здійснюється перетворення одного символу вхідного алфавіту Z={z₁,z₂,…,z_F} в один символ вихідного алфавіту W={w₁,w₂,…,w_G} та стрибковий перехід автомата зі стану q(t_і) в стан q(t_і+1). Поняття автоматного часу випливає з описаного принципу дискретизації реального часу. Автоматний час є безрозмірною величиною та має цілочисельне значення, мірою якого є кількість тактів.

Будь-який дискретний пристрій обробки інформації в загальному виді являє собою перетворювач, що здійснює перетворення вектора вхідних сигналів X=(x₁,x₂,…,x_n) в вектор вихідних сигналів Y=(y₁,y₂,…,y_m). На рис. 4.2 такий пристрій представлено у вигляді “чорного” ящика.

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

У всіх пристроях збору, обробки та передачі інформації, що застосовуються в системах управління та автоматики, вхідні і вихідні сигнали подаються в цифровій формі, тобто у процедурах перетворення інформації об’єктом обробки є цифрові сигнали, над якими здійснюються обчислювальні операції або логічні перетворення. Логічні сигнали віднесені до цифрових на тій підставі, що вони є квантованими за двома рівнями і приймають числові значення 0 та 1 (алфавіт логічних змінних). База (упорядкований список n аргументів) логічної функції також є цифровим сигналом (n-розрядним). В подальшому в якості алфавітів вхідних і вихідних сигналів скінченних автоматів ми будемо використовувати алфавіт двійкової системи числення, тобто множину символів {0,1}.

Відзначимо, що в літературних джерелах з дискретного аналізу зустрічаються назви “дискретний автомат”, “дискретний пристрій”, “пристрій дискретної дії”, що рівнозначні за сенсом узагальненій назві “скінченний автомат”, і використовуються в окремих випадках з метою віддзеркалення певних характеристичних ознак реальних автоматів. Якщо мова йде про дискретні пристрої обчислювальної техніки та автоматики, вхідний та вихідний алфавіти яких являють собою множини цифр, то такі пристрої називають цифровими автоматами. Нижче ми дамо формалізовані означення скінченого та цифрового автоматів.

Оскільки предметом вивчення у даному розділі є елементи теорії абстрактних автоматів, надалі будемо користуватися термінами “скінченний автомат” або просто “автомат”. Продовжимо огляд видів автоматів.

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

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

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

Якщо принципом класифікації є механізм випадкового вибору, то розрізняють детерміновані та ймовірнісні (стохастичні) автомати. Поведінка детермінованого автомата в кожний момент дискретного часу визначається поточною входною інформацією та станом автомата в попередній момент часу. У детермінованих автоматах виконується умова однозначності переходів: якщо автомат знаходиться в деякому стані q_i Q, де Q – множина станів, то під впливом довільного вхідного сигналу z_kÎZ автомат може перейти в один і тільки один стан q_jÎQ, причому ситуація q_i=q_j зовсім не виключається. У ймовірносних автоматах ця залежність пов’язана ще і з деяким випадковим вибором. Ймовірносний автомат — це дискретний перетворювач інформації, функціонування якого в кожний момент часу залежить тільки від стану пам’яті та описується статистичними законами. У ймовірнісних автоматах при впливі одного і того ж входного сигналу можливі переходи зі стану q_i в різні стани з множини Q із заданою ймовірністю.

Якщо принципом класифікації автоматів є обсяг пам’яті, то різниця полягає в тому, що автомат має скінченне або нескінченне число внутрішних станів. За цим принципом розрізняють наступні типи скінченних автоматів.

Автоматами 1-го типу, або комбінаційними схемами (КС), прийнято називати такі автомати, сукупність вихідних сигналів яких визначається тільки комбінацією вхідних сигналів у поточний момент часу t_i і не залежить від сигналів, що надходили на входи автомата в попередні моменти часу. Такі автомати називають також автоматами без пам'яті або скінченними функціональними перетворювачами. З автоматами цього типу ми зустрічалися, розглядаючи технічні засоби реалізації логічних функцій (розд. 2, п. 2.4).

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

сукупність вихідних сигналів автомата з пам’яттю залежить не тільки від вхідного впливу, але й від стану автомата в поточний та попередній моменти часу. Цими ж факторами визначається і той стан, в який автомат переходить.

Якщо скінченний автомат забезпечити (теоретично) необмеженою пам'яттю, то отримаємо автомат 3-го типу – нескінчений автомат, який називається машиною Тьюринга. За допомогою машини Тьюринга можна реалізувати будь-який алгоритм перетворення інформації. Нескінчений автомат являє собою певну математичну ідеалізацію скінченного автомата, який має нескінченне число станів. Абстрактний автомат–машина Тьюринга є нескінченним, але ЕОМ або її окремі частини є скінченними автоматами.