Основні поняття теорії абстрактних автоматів

Тема  1. Абстрактні автомати 

Лекція  1.1. Основні поняття теорії абстрактних автоматів

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

    Розглянемо  деякі питання класифікації автоматів. Все ЦА можна розділити на два основні класи: автомати без пам'яті або примітивні автомати і автомати з пам'яттю.

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

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

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

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

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

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

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

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

    Абстрактний автомат працює в дискретному  часі, який задається цілими позитивними числами  t = 0, 1, 2, …

    У кожний момент дискретного часу  t, який зветься тактом, автомат перебуває у деякому стані з множини станів автомата Q.

    У початковий момент часу (t = 0) він завжди знаходиться в стані q_s . Вважається, що реакція автомата на вхідні сигнали не залежить від інтервалів часу між тактовими моментами часу.

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

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

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

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

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

    До  речі, терміни "скінчений автомат" і "цифровий автомат" часто використовуються як синоніми і по суті виражають одне і те ж поняття.

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

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

      Нескінченний  автомат – абстрактний автомат, хоч би одна з множин X, Y, Q якого нескінченна.

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

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

Абстрактний скінчений автомат визначають як шістку (кортеж) M = (Q, X, Y, δ, λ, q_s) де

1. Q ={q₁, q₂, ... ,q_m}- cкінчена множина станів (алфавіт станів);
2. X ={x₁, x₂, ... ,x_r}- cкінчена множина вхідних сигналів (вхідний алфавіт);
3. Y ={y₁, y₂, ... ,y_k}- скінчена множина вихідних сигналів (вихідний алфавіт);
4. δ - функція переходу, : Q(t+1) = δ(Q(t), X(t));
5. λ- функція виходу , яку найчастіше визначають одним з двох альтернативних способів:
1. Y(t) = λ₁(Q(t), X(t)) – автомат Мілі,
2. або Y(t) = λ₂(Q(t)) – автомат Мура ;
6. q_s - (входить до складу Q) - початковий стан.

Таким чином, автомат Мілі відрізняється від автомату Мура змістом λ. У автомата Мілі, вихідні сигнали визначаються переходами зі стану до стану, а в автоматі Мура  - саме станами. Автомати названі за іменами американських вчених G.H. Mealy и E.F. Moore. Модель Милі дозволяє досягти тих же результатів при меншому кількості станів, але частіше застосовується простіша модель Мура.

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

      Існує третій тип автоматів, так званий С-автомат, який містить функції виходу двох типів: Y₁(t)=λ₁(Q(t), X(t)) і Y₂(t)=λ₂(Q(t)). Абстрактний С- автомат можна представити у вигляді пристрою з одним входом, на який надходять сигнали з вхідного алфавіту X, і двома виходами, на яких з'являються сигнали з алфавітів двох. Відзнака С - автомата від моделей Мілі і Мура полягає в тому , що він одночасно реалізує дві функції виходів l₁ и l₂, кожна з яких характерна для цих моделей окремо. 

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

      Абстрактний автомат має один вхід і один вихід. Автомат працює в дискретному часі, який приймає цілі позитивні значення t = 0,1,2,... В кожен момент t дискретного часу автомат знаходиться в деякому стані q(t) з множини станів автомату, причому в початковий момент t = 0 він завжди знаходиться в початковому стані.

      Сенс поняття абстрактного автомата полягає в тому, що він реалізує деяке відображення множини слів вхідного алфавіту X у множину слів вихідного алфавіту Y. Тобто якщо на вхід автомата, встановленого в початковий стан q_s, подавати буква за буквою деяку послідовність букв вхідного алфавіту (вхідне слово), то на виході автомата послідовно з'являтимуться букви вихідного алфавіту (вихідне слово).

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

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

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

1. повністю визначені та часткові;
2. детерміновані і ймовірнісні;
3. синхронні та асинхронні;

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

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

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

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

      Для визначення синхронних і асинхронних автоматів вводиться поняття сталого стану. Стан автомата називається сталим, якщо потрапивши в цей стан під дією деякого сигналу x_j автомат вийде з нього лише під дією іншого сигналу x_k, відмінного від x_j.

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

      Структурний автомат  - скінчений автомат, внутрішній устрій якого відомий.