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

     При практичній реалізації цифрових автоматів  вони можуть бути реалізовані 

     трьома  різними способами:

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

    Переваги  і недоліки автоматів  з жорсткою логікою.

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

    Переваги  і недоліки автоматів  з мікропрограмною  логікою.

    Перевагою автоматів з мікропрограмною логікою є простота реалізації і особливо простота проектування.

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

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

    Переваги і недоліки автоматів з програмною логікою.

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

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

    Теорію  автоматів прийнято ділити на дві  основні частини: абстрактну і структурну.

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

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

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

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

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

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

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

      Приклад автомату Мілі: Прилад з продажу цукерок

Розробимо автомат приладу, який видає цукерку, якщо достатня кількість монет буде отримана та поверне відповідну решту. Визначимо V = ({0c, 5c, 10c, 15c}, {n, d, q}, {c₀, c₁, c₂, c₃, c₄}, δ, λ, 0c}. V визначає автомат приладу, що продає цукерки вартістю 20 центів.

Mealy machine V

Автомат має  чотири стани 0c, 5c, 10c, and 15c, кожний з яких відповідає кількості грошей кинутих у прилад 0¢, 5¢, 10¢, та 15¢. Вхідний алфавіт містить n, d, and q, що визначає монети у 5 (nickels), 10 (dimes) та 25 (quarters) центів відповідно. У вихідному алфавіті λ визначає стан, коли прилад не видає цукерок („очікує”), а стани c₀, c₁, c₂, c₃, and c₄ визначають відповідно видачу цукерки без здачі, цукерки та однієї монети, цукерки та двох монет, цукерки та трьох монет, цукерки та чотирьох монет по 5 центів як здачу.

Нехай будуть кинуті монети у 5+10+25 центів, тобто вхідне слово - ndq. Автомат починає працювати зі стану 0c, тому що жодної монети ще не кинуто у прилад. кинути першу монету у 5 центів (a nickel). Автомат виконує перехід „n ; λ” зі стану 0c до стану 5c, фіксуючі що 5 центів були кинуті. Перехід не генерує видачу цукерки (вихідний сигнал λ), тому що грошей ще недостатньо. Автомат починає працювати зі стану 0c, тому що жодної монети ще не кинуто у прилад.

додати наступну монету у 10 центів (a dime). Автомат виконує перехід „d ; λ” зі стану 5c у стан 15c, підтверджуючі, що that 15 центів накопичено. І знову перехід не генерує вихідного сигналу бо недостатньо грошей кинуто у прилад. Натискуємо Step щоб кинути останню монету у 25 центів (quarter).

Автомат виконує  перехід „q ; c_4” зі стану 15c у 0c, повертаючись до первинного стану. Перехід видає, нарешті, вихідний сигнал c₄, та прилад видає покупцю цукерку і чотири монети по 5 центів.

      Приклад автомату Мура: ділення навпіл двійкового числа

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

Граф переходів  автомату може виглядати таким чином:

Автомат Мура для ділення навпіл двійкового числа

Ми маємо 4 можливих комбінації двох останніх бітів 00, 01, 10 та 11, які представлені відповідними станами автомата. Наприклад, стан 01 означає що останній отриманий вхідний біт був 1, та передостанній дорівнював 0. Кожний стан формує вихідний сигнал, який дорівнює  передостанньому вхідному біту і очікує наступний вхідний сигнал, який визначає перехід до наступного стану.

Припустимо рядок  вхідних сигналів/символів виглядає як "101".

Автомат обробив  перший символ, "1", і перейшов зі стану 00 до стану 01. Стан 01 виробив вихідний сигнал "0". Хоча стан 01 виробив такий самий вихідний сигнал, як і початковий стан 00, в цьому є різниця, тому що він пам’ятає, що останнім символом на вході був "1". Це викликає різні переходи за тими самими вхідними сигналами.

Зверніть увагу  на те, що всі переходи зі стану 01 спрямовані тільки на ті стани, які виробляють вихідний сигнал "1". Це еквівалентно зсуву бітів вправо. Натискуємо Step для обробки наступного біту.

    Автомат обробляє вхідний символ "0" і за переходом 0 потрапляє у стан 10. Стан 10 генерує вихідний сигнал/символ "1", який відповідає попередньому вхідному біту "1". Цей стан тепер „пам’ятає”, що останній вхідний біт був "0" і тому всі переходи з цього стану спрямовані лише на стани, які виробляють вихідні сигнали "0".

    Автомат обробив останній біт "1"та за переходом 1 потрапив до стану 01, який, у свою чергу, виробив вихідний сигнал "0", завершуючи видачу. Хоча останній вхідний символ був "1", він ігнорується.