Зміст
1. Абстрактні цифрові автомати
1.1 Основні поняття
1.2 Типи абстрактних автоматів
1.3 Способи завдання абстрактних автоматів
1.4 Зв'язок між моделями Мілі і Мура
1.5 Еквівалентні автомати. Еквівалентні перетворення автоматів
1.6 Мінімізація числа внутрішніх станів автомата
Висновок
Список літератури
Введення
Тема контрольної роботи з дисципліни "Прикладна теорія цифрових автоматів "-" Абстрактні цифрові автомати ".
Мета роботи - ознайомиться з основними поняттями абстрактних цифрових автоматів; типами абстрактних автоматів; способами завдання абстрактних автоматів; зв'язком між моделями Мілі і Мура; еквівалентними автоматами і еквівалентними перетвореннями автоматів; мінімізацією числа внутрішніх станів автомата і алгоритмом Ауфенкампа-Хона.
1. Абстрактні цифрові автомати 1.1 Основні поняття
Цифровий автомат можна трактувати як пристрій, що здійснює прийом, зберігання і перетворення дискретної інформації по деякому алгоритму. З певної точки зору до автоматів можна віднести як реальні пристрої (ЕОМ), так і абстрактні системи (математичні моделі).
Автоматом називається дискретний перетворювач інформації, здатний приймати різні стани, переходити під впливом вхідних сигналів з одного стану в інший і видавати вихідні сигнали.
Загальна теорія автоматів підрозділяється на абстрактну і структурну.
Абстрактна теорія автоматів, відволікаючись від структури автомата (Тобто не цікавлячись способом його побудови), вивчає лише поведінку автомата щодо зовнішнього середовища. Абстрактна теорія автоматів близька до теорії алгоритмів, будучи по суті її подальшою реалізацією.
На противагу абстрактній теорії автоматів, структурна теорія автоматів цікавиться як структурою самого автомата, так і структурою вхідних впливів і реакцій автомата на них. У структурній теорії вивчаються способи побудови автоматів, способи кодування вхідних впливів і реакцій автомата на них. Структурна теорія автоматів є продовженням і розвитком абстрактної теорії. Спираючись на апарат булевих функцій і на абстрактну теорію автоматів, структурна теорія дає ефективні рекомендації з розробки реальних пристроїв обчислювальної техніки.
Абстрактний цифровий автомат (ЦА) є математичною моделлю дискретного керуючого пристрою.
Абстрактний ЦА визначається безліччю, що складається з шести елементів:
S = {X, A, Y,, a o },
де:
X = {x 1 , x 2 ,. x n } - Множина вхідних сигналів (вхідний алфавіт);
Y = {y 1 , y 2 , y m } - безліч вихідних сигналів (вихідний алфавіт);
А = {a 0 , a 1 , a 2 ,. а N } - Безліч станів (алфавіт станів);
а про - початковий стан (а про А);
- функція переходів автомата, що задає відображення (ХхА) А, тобто ставить у відповідність будь парі елементів декартового добутку (ХхА) елемент множини А;
- функція виходів автомата, що задає або відображення (XxA) Y, або відображення AY.
Іншими словами, функція переходів показує, що автомат S, перебуваючи в деякому стані а j А, при появі вхідного сигналу х j Х переходить в деякий стан а р А. Це можна записати:
a p = (a i , X j ).
Функція виходів показує, що автомат S, перебуваючи в деякому стані а j А, при появі вхідного сигналу х j Х видає вихідний сигнал у k Y. Це можна записати: у k = (a i , X j ).
Поняття стан у визначення автомата було введено у зв'язку з тим, що часто виникає необхідність в описі поведінки систем, виходи яких залежать не тільки від стану входів в даний момент часу, але і від деякої передісторії, тобто від сигналів, які надходили на входи системи раніше. Стан як раз і відповідає деякій пам'яті про минуле, дозволяючи усунути час як явну змінну і виразити вихідні сигнали як функцію станів і входів в даний момент часу.
Абстрактний автомат функціонує в дискретному автоматному часу t = 0,1,2,. і переходи зі стану в стан здійснюються миттєво. У кожен момент t дискретного часу автомат знаходиться в певному стані a (t) з безлічі А станів автомата, причому в початковий момент часу t = 0 він завжди знаходиться в початковому стані а про . У момент часу t, будучи в стані a (t), автомат здатний сприйняти на вхідному каналі сигнал х (t) X, і видати на вихідному каналі сигнал y (t) = (a (t), x (t)), переходячи в стан a (t +1) == (a (T), x (t)). Залежність вихідного сигналу від вхідного і від стану означає, що в його складі мається пам'ять.
1.2 Типи абстрактних автоматів
За способом формування функції виходів виділяють три типи абстрактних автоматів: автомат Мілі, автомат Мура, С-автомат. Автомат Мілі характеризується системою рівнянь:
y (t) = (A (t), x (t));
a (t +1) = Оґ (a (t), x (t)). (1-1)
Автомат Мура - системою рівнянь:
y (t) = (A (t));
a (t +1) = Оґ (a (t), x (t)). (1-2)
С-автомат - системою рівнянь:
у = y 1 y 2
y 1 (t) = (a (t), x (t));
У 2 (t) = 2 (A (t));
a (t +1) = Оґ (a (t), x (t)).
Довільний абстрактний автомат Мілі або Мура (рис.1.1.) має один вхідний і один вихідний канали. Довільний абстрактний С-автомат має один вхідний і два вихідних х каналу (рис.1.2.).
Малюнок 1.1 - Абстрактний автомат
Рісунок.1.2 Абстрактний С-автомат
Якщо на вхід абстрактного автомата Мілі або Мура, встановленого в початковий стан а про , подавати буква за буквою деяку послідовність букв вхідного алфавіту х (0), х (1),. - Вхідна слово, то на виході автомата будуть послідовно з'являтися літери вихідного алфавіту у (0), у (1),. - Вихідна слово. Для випадку С-автомата на його виходах будуть з'являтися дві послідовності: y 1 (0), y 1 (1),. і y 2 (0), y 2 (1),. В абстрактному З - Автоматі вихідний сигнал y 2 (t) = (a (T)) видається весь час, поки автомат знаходиться в стані a (t). Вихідний сигнал y 1 (t) = О» 1 (A (t), x (T)) видається під час дії вхідного сигналу x (t) при знаходженні С-автомата в стані a (t).
Таким чином, на рівні абстрактної теорії функціонування цифрового автомата розуміється як перетворення вхідних слів у вихідні слова.
Виділяють повністю визначені і часткові автомати.
Повністю певним називається абстрактний цифровий автомат, у якого функція переходів або функція виходів, або обидві ці функції визначені для всіх пар переходів (x i , a j ).
Частковим називається абстрактний цифровий автомат, у якого функція переходів або функція виходів, або обидві ці функції визначені не для всіх пар переходів (x i , a j ).
Абстрактний цифровий автомат називається ініціальний, якщо на безлічі його станів А виділяється початковий стан а про .
1.3 Способи завдання абстрактних автоматів
Щоб задати кінцевий автомат S, необхідне описати всі елементи безлічі: S = {X, A, Y,,, a o }. Існує кілька способів завдання роботи автомата, але найбільш часто використовується табличний (матричний), графічний, аналітичний.
При табличному способі автомат задається двома таблицями: таблицею переходів і таблицею виходів, або матрицею з'єднань. Таблиця переходів довільного повністю визначеного автомата будується наступним чином: рядки таблиці позначают...
