Абстрактні цифрові автомати
1. Абстрактні цифрові автомати
1.1 Основні поняття
1.2 Типи абстрактних автоматів
1.3 Способи завдання абстрактних автоматів
1.4 Зв'язок між моделями Мілі та Мура
1.5 Еквівалентні автомати. Еквівалентні перетворення автоматів
1.6 Мінімізація числа внутрішніх станів автомата
Тема контрольної роботи з дисципліни "Прикладна теорія цифрових автоматів" - "Абстрактні цифрові автомати".
Мета роботи – ознайомиться з основними поняттями абстрактних цифрових автоматів; типами абстрактних автоматів; способами завдання абстрактних автоматів; зв'язком між моделями Мілі та Мура; еквівалентними автоматами та еквівалентними перетвореннями автоматів; мінімізацією числа внутрішніх станів автомата та алгоритмом Ауфенкампа-Хона.
1. Абстрактні цифрові автомати
1.1 Основні поняття
Цифровий автомат можна трактувати як пристрій, який здійснює прийом, зберігання та перетворення дискретної інформації за деяким алгоритмом. З певної точки зору до автоматів можна віднести як реальні пристрої (ЕОМ), і абстрактні системи (математичні моделі).
Автоматом називається дискретний перетворювач інформації, здатний приймати різні стани, переходити під впливом вхідних сигналів з одного стану до іншого та видавати вихідні сигнали.
Загальна теорія автоматів поділяється на абстрактну та структурну.
Абстрактна теорія автоматів, відволікаючись від структури автомата (тобто не цікавлячись способом його побудови), вивчає лише поведінку автомата щодо довкілля. Абстрактна теорія автоматів близька до теорії алгоритмів, будучи сутнісно її подальшою реалізацією.
Упротилежність абстрактної теорії автоматів, структурна теорія автоматів цікавиться як структурою самого автомата, і структурою вхідних впливів і реакцій автомата ними. У структурної теорії вивчаються методи побудови автоматів, методи кодування вхідних впливів і реакцій автомата ними. Структурна теорія автоматів є продовженням та розвитком абстрактної теорії. Спираючись на апарат булевих функцій та абстрактну теорію автоматів, структурна теорія дає ефективні рекомендації щодо розробки реальних пристроїв обчислювальної техніки.
Абстрактний цифровий автомат (ЦА) є математичною моделлю дискретного керуючого пристрою.
Абстрактний ЦА визначається безліччю, що складається з шести елементів:
X = 1, x2,. xn > - безліч вхідних сигналів (вхідний алфавіт);
Y=1 , y2 , ym > - множина вихідних сигналів (вихідний алфавіт);
А=< a0, a1, a2,. аN > - множина станів (алфавіт станів);
Іншими словами, функція переходів
Поняття стан визначення автомата було введено у зв'язку з тим, що часто виникає необхідність в описі поведінки систем, виходи яких залежать не тільки від стану входів в даний момент часу, але і від деякої передісторії, тобто. від сигналів, що надходили на входи системи раніше. Стан якраз і відповідає деякій пам'яті про минуле, дозволяючи усунути час як явну змінну та виразити вихідні сигнали як функцію станів та входів на даний момент часу.
Абстрактний автомат функціонує у дискретному автоматичному часі t=0,1,2,. та переходи зі стану в стан здійснюються миттєво. У кожен момент tдискретного часу автомат знаходиться у певному стані a(t) з множини А станівавтомата, причому у початковий момент часу t=0 він завжди знаходиться у початковому стані ао . У момент часу t, будучи в стані a(t), автомат здатний сприйняти на вхідному каналі сигнал х(t)
1.2 Типи абстрактних автоматів
За способом формування функції виходів виділяють три типи абстрактних автоматів: автомат Милі, автомат Мура, С-автомат. Автомат Мілі характеризується системою рівнянь:
a(t+1) = δ(a(t), x(t)). (1-1)
Автомат Мура – системою рівнянь:
a(t+1) = δ(a(t), x(t)). (1-2)
С-автомат – системою рівнянь:
Довільний абстрактний автомат Милі або Мура (рис.1.1) має один вхідний і один вихідний канали. Довільний абстрактний С-автомат має один вхідний і два вихідних канали (рис.1.2.).
Малюнок 1.1 - Абстрактний автомат
Малюнок.1.2 Абстрактний С-автомат
Якщо на вхід абстрактного автомата Милі або Мура, встановленого в початковий стан ао , подавати буква за буквою деяку послідовність букв вхідного алфавіту x (0), x (1),. - вхідне слово, то на виході автомата будуть послідовно з'являтися букви вихідного алфавіту у (0), (1),. - Вихідне слово. Для випадку С-автомата на його виходах з'являтимуться дві послідовності: y1 (0), y1 (1),. та y2 (0), y2 (1),. В абстрактному С - автомат вихідний сигнал y2 (t) =
Таким чином, на рівні абстрактної теорії функціонування цифрового автомата сприймається як перетворення вхідних слів у вихідні слова.
Виділяють цілком певні та часткові автомати.
Цілком певним називається абстрактний цифровий автомат, у якого функція переходів або функція виходів, або обидві ці функції визначені всім пар переходів (xi ,aj ).
Частковим називається абстрактнийцифровий автомат, який має функцію переходів або функцію виходів, або обидві ці функції визначені не для всіх пар переходів (xi ,aj ).
Абстрактний цифровий автомат називається ініціальним, якщо на множині його станів А виділяється початковий стан ао.
1.3 Способи завдання абстрактних автоматів
Щоб встановити кінцевий автомат S, необхідно описати всі елементи множини: S=< X,A,Y,
При табличному методі автомат задається двома таблицями: таблицею переходів і таблицею виходів, або матрицею сполук. Таблиця переходів довільного повністю визначеного автомата будується так: рядки таблиці позначаються буквами вхідного алфавіту автомата, а стовпці таблиці - літерами алфавіту станів автомата; У клітині таблиці переходів, що знаходиться на перетині рядка, зазначеної вхідним сигналом xi , і стовпця зазначеного станом aj ставиться стан аk , що є результатом переходу автомата зі стану aj під впливом вхідного сигналу хi , що визначається виразом ak =