Класифікація і характеристика автоматів

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

Автомати можна класифікувати за різними ознаками.

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

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

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

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

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

Рисунок 1.1- До визначення вхідних та вихідних змінних реального (а)

та абстрактного (б) автоматів

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

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

Автоматний час найбільш зручно представляти у вигляді ряду натуральних позитивних чисел: t =1, 2, 3,.. n. Таким чином, абстрактний автомат працює у дискретному часі, де кожний момент дискретного часу зветься тактом.

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

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

Наприклад: в алфавіті X = (x₁, x₂), що складається з двох букв, словами будуть: x₁, x₂, x₁x₁, x₁x₂, x₂x₁, x₂x₂, x₁x₁x₁ і так далі.

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

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

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

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

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

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

Частковим випадком дискретних автоматів є автомати, що мають лише один внутрішній стан. Такі автомати називаються комбінаційними схемами або автоматами без пам'яті. Робота таких автоматів полягає в тому, що вони зіставляють кожному вхідному сигналу x(t) вихідний сигнал y(t).

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

Другий великий клас схем пристроїв містить у своєму складі елементи пам'яті. Ці схеми називаються цифровими автоматами (ЦА) з пам’яттю. У ЦА вихідні сигнали в даний момент часу залежать не лише від значення вхідних сигналів в той же момент часу, але і від стану схеми, який, у свою чергу, визначається значеннями вхідних сигналів, що поступили в попередні моменти часу. Тобто вводиться поняття - стан. Для того, щоб зберігати дані про стан, в якому знаходиться пристрій в ЦА використовуються елементи пам'яті - тригери.

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

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

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

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

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

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

Здебільшого асинхронні автомати будуються на основі асинх­ронних елементів пам'яті - асинхронних тригерів. Синхронні ав­томати будуються з використанням синхронних тригерів.

По виду діяльності - автомати діляться на: інформаційні, управління і обчислювальні.

До інформаційних автоматів відносяться різноманітні довідкові таблиці, інформаційні табло, пристрої аварійної сигналізації.

До автоматів, управління, прийнято відносити пристрої для управління деяким процесом.

До обчислювальних автоматів відносяться мікрокалькулятори, процесори в ЕОМ і інші пристрої, що виконують обчислення.

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

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

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

У імовірнісних автоматах ця залежність пов'язана ще і з деяким випадковим вибором.

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