Абстрактні автомати. Автомати Мілі та Мура

Размещено на http://www.allbest.ru/

Міністерство освіти, науки, молоді та спорту України

Технічний коледж

Національного університету «Львівська політехніка»

Відділення інформаційних технологій

та комп'ютерної техніки

Реферат на тему

Абстрактні автомати. Автомати Мілі та Мура

Виконав: студент групи 34 ПЗ

Кіндрат Назарій

Прийняв: викладач

Соловйов С.О.

Львів 2012

План

1. Абстрактний автомат як модель послідовних схем

2. Синтез абстрактних автоматів

1. Абстрактний автомат як модель послідовних схем

У комбінаційних схемах вихідний сигнал залежить тільки від набору вхідних змінних. Наприклад, якщо у ДНФ функції у₁=1 входить терм F₁= abc, то в будь-який момент часу у₁=1 при виконанні рівності a = b = c = 1. Проте існує клас пристроїв, вихідна інформація в яких залежить від вхідних сигналів, що надходять в усі попередні моменти часу. Такі пристрої називаються послiдовними схемами. Характерним прикладом послідовної схеми є лічильник. Якщо в деякий момент часу t в лічильнику знаходиться число 0, то під час вступу одиниці на вхід (момент t+1 ) в лічильнику буде 1. У момент часу t+2 при вступі одиниці на вхід па виході буде 2. Якщо ж у момент часу t 2 надходить нуль, то лічильник, як і раніше генерує число 1. Таким чином, вихід лічильника залежить від деякої передісторії надходження вхідних сигналів у часі. До цього ж класу відносяться системи управління, що реалізують деякі алгоритми.

Перші елементи теорії послідовних схем з'явилися в роботах Дж. Хаффмана в 1954 році. Основними авторами цієї теорії були Стівен Кліні, Едвард Мур, Джордж Милі, М.А. Еаврілов, В.М. Глушков. У роботі Хліні «Reprcsentation of events in nerve sets and finite automata» (1956р.) був введений термін кінцевий автомат для послідовних схем. Американські вчені Мілі (1955) і Мур (1956) розглянули два типи автоматів, названих потім їх іменами. Теорія кінцевих автоматів була доведена до рівня практичного застосування в роботах академіка В.М. Глушкова (1923-1982 рр), що вийшли в 1960-962 роках.

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

Абстрактний автомат є математичною моделлю цифрового пристрою і задається вектором:

S = {A,Z,W,д,л,a₁}. (17.1)

В вираз (17.1) входять наступні компоненти: А = {а₁,..., а_M} - множина внутрішніх станів автомата;

Z = {z₁,..., z_F) - безліч вхідних сигналів; д - функція переходів, що реалізує відображення множини в A (a_s= д(a_M, z_f), де a_M, a_S A, z_f Z); л - функція виходів, що реалізує відображення множини в W(щ_g = л(a_M, z_f)), де , , ); - початковий стан автомата. Множини А, Z, W іноді називаються алфавітами абстрактного автомата.

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

щ(t) = л(z(0),z(l),...,z(t)), (17.2)

де щ(t) - вихідний сигнал в момент часу t, z(i) - вхідний сигнал в момент часу i=0,1 ,...,t. Формули виду (17.2) є надзвичайно громіздкими і не дозволяють компактно задати закон функціонування автомата. Якщо стан a(t) є деякою функцією вхідних сигналів z(0 ),..., z, z (t -1), то формулу (17.2) можна спростити до формули

. (17.3)

Стан a(t) у формулі (17.3) Може бути визначене за використання вихідного стану a₁ = а(0) і функції переходів л:

(17.4)

Формула (17.4) свідчить, Що для визначення стану в будь-який момент t досить знати початковий стан (а він унікальний) і послідовність вхідних сигналів z(0), z(1),..., z, z (t-1).

Абстрактний автомат ( мал.17.1) має один вхідний канал і один вихідний канал.

мал.17.1. Абстрактний автомат

У момент часу t = 0 автомат знаходиться в початковому стані a є А. Нехай в момент часу t автомат знаходиться в стані a(t) = а_m і на вхід автомата надходить буква вхідного алфавіту z(t) = z_f. Автомат формує вихідний сигнал щ(t) = л(a_m, z_f-) = щ_g і переходить в стан a(t+1)=д(a_m,z_f). Таким чином, абстрактний автомат перетворить букви вхідного алфавіту в літери вихідного алфавіту. Це означає, що абстрактний автомат є найбільш загальною моделлю пристрою переробки інформації.

Найбільшого поширення на практиці отримали три типи автоматів:

1. Автомат Мілі, що задається рівняннями

a(t+l) = д(a(t), z (t)); (17.5)

щ(t)=л(a(t),z(t));

2. Автомат Мура, що задається рівняннями

a(t+1)=д(a(t),z(t)); (17.6)

щ(t)=л(a(t));

3. Комбінаційна схема, що задається рівняннями

A= {a₁}; (17.7)

щ(t)=л(z(t));

Методи завдання, мінімізації та синтезу комбінаційних схем розглянуті раніше, тому розглянемо докладніше методи, пов'язані з автоматами Мілі і Мура. Обмежимося розглядом повністю певних автоматів, для яких рівняння (17.5) - (17.6) визначені для всіх пар декартового добутку множин станів і вхідних літер: AxZ = {(a1, z1), (a1, z2 ),...,( a1,z_F) ...,( a_M, z_F)}.

Існує два основні методи задання автоматів - табличний і графічний.

1. Табличне задання автомата Мілі. Автомат Мілі задається таблицями переходів і виходів, які в загальному випадку представлені таблицями 17.1 та 17.2 відповідно. Рядки цих таблиць відзначаються вхідними сигналами , а стовпці - станами автомата . На перетині рядка z_f та стовпця а_m в таблиці переходів записується стан переходу a_s = д(a_m, z_f), а в таблиці виходів - вихідний сигнал щ_g = л(a_m, z_f).

Таблиця 17.1 Загальний вигляд таблиці переходів автомата Мілі

Таблиці переходів та виходів у сукупності містять всю інформацію про абстрактне автоматі, тобто визначають всі компоненти безлічі (17.1), включаючи рівняння (17.5).

Таблиця 17.2 Загальний вигляд таблиці виходів автомата Мілі

Таблиці переходів та виходів у сукупності містять всю інформацію про абстрактне автоматі, тобто визначають всі компоненти безлічі (17.1), включаючи рівняння (17.5).

Наприклад, з табл. 17.3 і 17.4 для автомата S₁ маємо А = {a₁,a₂,a₃}, Z = {z₁, z₂}, W={щ₁, щ₂, щ₃}.

Таблиця 17.3 Таблиця переходів автомата Мілі S₁

Таблиця 17.4 Таблиця виходів автомата Мілі S₁

З таблиці. 17.3 маємо, наприклад, д(а₂, z₁) = a₃, д(a₁, z₁) = а₂. З таблиці. 17.4 маємо, наприклад, л(a₁,z₁)=щ₁, л(a₃,z₂) = щ₂.

Оскільки рядки і стовпці таблиць переходів і виходів відзначені однаковим чином, то всю інформацію про автомат Мілі можна задати однієї суміщеної таблицею переходів і виходів. У цій таблиці (Табл. 17.5 для автомата S1) на перетині рядка zf і стовпця а_m знаходяться і стан переходу a_s= д (a_m, zf) і вихідний сигнал щ_g = л (a_m, zf).

Таблиця 17.5 Поєднана таблиця переходів і виходів автомата Мілі S₁

2. Графічне задання автомата Мілі. Граф автомата представляє собою орієнтований зв'язний граф, вершини якого відповідають станам автомата, а ребра (дуги) - переходам між станами. У автоматі Мілі дуга, відповідна переходу з а_m в а_z під впливом сигналу zf , відзначається вихідним сигналом щ_g = л (a_m, z_f) і вхідним сигналом zf (рис 17.2). Граф автомата Мілі S₁(Мал. 6.3) маємо три вершини і шість дуг, що відповідає твору М · F.

мал.17.2. Фрагмент графа автомата Мура

мал.17.3. Граф автомата Мілі S₁

3. Табличне задання автомата Мура. Як випливає з рівнянь (17.6), вихідний сигнал автомата Мура залежить тільки від його стану. Тому автомат Мура задасться однієї зазначеної таблицею переходів (Табл. 17.6).

Таблиця 17.6 Загальний вигляд переходів автомата зазначеної таблиці Мура

Наприклад, з табл. 17.7 слідують всі елементи множини S автомата Мура S2: A = {a₁,a₂, a₃},

М = 3, Z = {z₁, z₂}, F = 2, W = {w₁, w₂), G = 2, д(a₁, z₁)= a₂, л(a₁) = л(а₃) = w₂ і т.д.

4. Графічне задання автомата Мура. Так як вихідні сигнали автомата Мура залежать тільки від вхідних станів, то кожній вершині графа автомата (Мал. 17.4) ставиться у відповідність вихідний сигнал.

Таблица 17.7 Зазначена таблиця переходів автомата Мура S₂

Так як вихідні сигнали автомата Мура залежать тільки від вхідних станів, то кожній вершині графа автомата (Мал. 17.4) ставиться у відповідність вихідний сигнал.

мал.17.4. Фрагмент графа автомата Мура

Дуга графа автомата Мура відзначається тільки вхідним сигналом. Граф автомата Мура S2 наведено на мал.17.5.

Як видно з мал.17.5, деякі дуги утворюють петлі. Стани, відповідні петлям, називаються чекають. Автомат буде залишатися у режим стані до тих пір, поки не зміниться значення вхідного сигналу. Так, для стану а₂ маємо д(a₂, z₂) = a₂ тобто автомат S₂ буде перебувати в стані а₂ поки вхідний сигнал не стане рівним z₁.

мал.17.5. Граф автомата Мура S₂.

2. Синтез абстрактних автоматів

Метод синтезу абстрактного автомата включає наступні етапи:

1. Формування таблиці істинності комбінаційної схеми,

виконує аналогічну обробку паралельної інформації.

2. Формування вхідного і вихідного алфавіту.

3. Формування графа автомата.

Розглянемо деякі приклади синтезу абстрактних автоматів.

Приклад 17.1. Синтезувати абстрактний автомат Мілі S₃, на вхід якого надходить трьох-розрядного послідовний код x₁,x₂,x₃, починаючи з розряду х₁. Якщо код містить дві послідовні одиниці, то необхідно сформувати сигнал у₁= 1, у противному випадку формується сигнал у₁ = 0.

Побудуємо таблицю істинності для відповідної паралельної комбінаційної схеми (Табл. 17.8), тобто схеми, на вхід якої сигнали х₁х₂х₃ надходять одночасно.

Таблиця 17.8 Таблиця істинності паралельної КС

Щоб отримати вхідний алфавіт, проаналізуємо стовпці х₁ - х₃ таблиці. У кожному стовпці перебувати або 0, або 1. Таким чином, вхідний алфавіт складається з двох символів: z₁ відповідає х₁ = 0, z₂ відповідає x_l = 1, де l = 1,2,3.

Інформація на вхід схеми надходить послідовно, тому, наприклад, змінна х₁ не дозволяє визначити вихідний сигнал. Якщо протягом двох тактів прийшла комбінація 00, то необхідно встановити y₁ = 0, а якщо 11, то у₁ = 1. Якщо приходить комбінація 01, то стан виходу невідомо. Таким чином, вихідний алфавіт автомата S3 містить 3 букви: w₁, якщо у₁ = 0, w₂, якщо у₁ = 1, w₃, якщо вихідний сигнал ще не визначений. Отже, для автомата S₃ маємо Z = {z₁, z₂}, W = {w_1,w₂,w₃}.

Розглянемо процес побудови графа автомата S₃. У момент часу t = 0 автомат знаходиться в стані а₁ ( мал.17.6а).

У момент часу t = 0 на вхід автомату можуть прийти сигнали z₁ або z₂. Якщо Z (0) = z₁, то x₁ = 0 і це відповідає рядками 1 - 4 таблиці істинності. У рядках 1 - 4 функція може мати будь-яке значення, отже, перехід {a₁, z₁) повинен бути відзначений невизначеністю (рис.17.6 б). Аналогічно, якщо Z (0) = z₂, то x₁ = 1, що відповідає рядкам 5-8 табл. 17.8. Цей перехід також відзначається вихідним символом, відповідним невизначеності (рис.17.6 б). Отже, маємо наступні переходи а(1) = а₂ = д (a ₁, z₁) або а(1) =a₃=д(a₁,z₂), і виходи автомата л(a₁,z₁)= л(a₁,z₂)= w(0)=w₃ (рис.17.6 б).

Якщо в момент часу t = 1 автомат знаходиться в стані а₂, то сигнал z₁ відповідає ситуації x₁x₂ = 00, так як а₂ відповідає історії x₁ = 0. У цьому разі комбінація вхідних сигналів (рядки 1 або 2 таблиці істинності) не може утримувати двох послідовних одиниць і необхідно сформувати сигнал w₁.

мал.17.6. Процес побудови графа автомата S₃

Розпізнавання вхідної комбінації завершено, і автомат повинен повернутися в стан а₁, щоб мати можливість обробляти наступну вхідну послідовність (мал.17.6 в). Якщо ж на вхід автомата приходить сигнал z₂, то це відповідає ситуації х₁х₂ = 01) (рядки 3 і 4), яка є невизначеною. Автомат переходить в стан а₄, відповідне історії 01, і формує сигнал w₃, що відображено на мал.17.6 в. Вхідні букви можуть приходити в таких послідовностях, які визначать іншу зміну станів.

Якщо в момент часу t= 1 автомат знаходиться в стані а₃ (історія х₁ = 1), то по вхідному сигналу z₁{х₁ х₂ = 10) автомат переходить в стан a₁ і формує вихідний сигнал w₁, що відповідає рядкам 5 і 6 вихідної таблиці істинності (мал.17.6 г). Якщо вхідний сигнал z (l) = z₂, то це відповідає рядкам 7 і 8 табл. 17.8. У цьому випадку автомат формує сигнал w₂ і переходить у стан а₁ (мал.17.6 г). Якщо автомат знаходиться в стані ац (t = 2), то прихід букви zj означає набір 010, а прихід z₂ - 011 ( мал.17.6 д).

Тепер можна зібрати повний граф абстрактного автомата S₃, поєднавши окремі підграфи ( мал.17.6), починаючи з стану a₁. Процес такої збірки не представляє особливих труднощів. Спочатку малюється граф, отриманий для переходів зі стану а₁ ( мал.17.6 б). Тепер до станів а2 і, а3 домальовують відповідні підграфи, представлені на мал.17.6 в і мал.17.6 г. Далі вершина а₄ розглядається, як початок підграфа, який зображений на мал.17.6 д. Цей підграф приєднується до вже отриманого графу. Після цього приєднання процес побудови графа автомата закінчується. Граф автомата Мілі S₃ наведено на мал.17.7, а поєднана таблиця переходів і виходів показана в Табл. 17.9.

мал.17.7. Граф автомата Мілі S₃

цифровий абстрактний автомат граф

Таблиця 17.9 Поєднана таблиця переходів і виходів автомата Мілі S3

З аналізу мал.17.7. і табл. 17.9 випливає, що безліч станів автомата S₃ містить чотири елементи - А = { a₁, a₂, a_3,a₄}, М = 4.

Приклад 17.2. Синтезувати абстрактний автомат Мура S₄, що виконує ті ж функції, що і автомат Мілі S₃.

Очевидно, що таблиця істинності паралельної КС для автомата S₄ збігається з табл. 17.8, а алфавіти Z і W автомата S₄ будуть наступними: Z = {z₁, z₂,} W = {w₁, w₂, i w₃}.

Розглянемо процес побудови графа автомата S₄. У момент часу t= 0 автомат знаходиться в початковому стані а(0) = a₁. Так як вхідна комбінація ще не ясна, стан a₁ відзначається вихідним сигналом w₃. За сигналом z₁(х₁ = 0) автомат переходить в стан a₂, для якого вихід не визначено, за сигналом z₂ - у стан a₃, в якому вихід автомата також не визначено (мал.17.8 а).

Якщо в момент часу t = 1 автомат знаходиться в стані а₂, то прихід букви z₁ означає ситуацію 00, за якою автомат переходить в стан a₄, зазначене вихідним сигналом w₁ (y₁ = 0). Якщо на вхід автомата приходить сигнал z₂, то це відповідає ситуації 01, для якої вихід ще не ясний. Автомат переходить у стан a₅, відповідне w₃ (мал.17.8 б). Якщо a (1) = a₃, то за сигналом z₁ автомат формує ознаку w₁ в стані a₆ а по сигналу z₂ - ознака w₂ в стані a₇ (мал.17.8 в).

Якщо a(2) = a₅, то сигнал z₁ визначає набір 010, тому автомат переходить в стан a₈ виходом w₁. Якщо вхідний сигнал дорівнює z₂, то це визначає набір 011, тому автомат переходить в стан a₉ і формує сигнал w₂ (мал.17.8 г).

Підграфи для станів a₄,a₆ - a₉ збігаються, тому що ці стани відповідають визначеним ситуаціям. У всіх випадках автомат переходить в стан a₁ незалежно від вхідних сигналів (мал.17.8 д - мал.17.8 е). Об'єднання фрагментів дасть граф автомата S₄ (мал.17.9).

мал.17.8. Процес побудови графа автомата S4

мал.17.9. Граф автомата Мура S4

Граф на мал.17.9 містить два стани а₁, що зроблено для більш наочного зображення. При цьому один із символів а₁ відповідає початковому стану, а другий - кінцевому. Знак * над дугою означає, що перехід не залежить від значень вхідних сигналів.

За цим графу (мал.17.9) будується зазначена таблиця переходів автомата Мура S₄ (Табл. 17.10).

Таблиця 17.10 Зазначена таблиця переходів автомата Мура S4

Автомати S₃ і S₄ виконують одну і ту ж функцію, тобто в цьому сенсі вони є еквівалентними. З аналізу графів автоматів S₃ і S₄ можна зробити виводи, що автомат Милі містить менше станів, чим еквівалентний автомат Мура, а також, що автомат Милі формує вихідні сигнали на один такт швидше, ніж еквівалентний автомат Мура. Ці виводи справедливі і в загальному випадку.

З аналізу графа автомата S₃ виходить, що для стану a₃ і a₄ по однакових вхідних сигналах формуються однакові вихідні сигнали і відбувається перехід в стан а₁, тобто:

л(a₃,z₁) = л(a₄,z₁)=w_1;

л(a₃,z₂) = л(a₄,z₂)=w_2;

д(a₃,z₁) = д (a₄,z₁)=a_1;

д (a₃,z₂) = д (a₄,z₂)=a_2;

Отже, стани a₃ і a₄ повністю ідентичні і одне з них можна виключити з графа автомата. Виключимо, наприклад, стан a₄, що приведе до мінімізованого графа (мал.17.10). Оскільки тепер стан а₃ замінює стан a₄, то всі переходи з a_s = а₄ замінюються на переходи з a₅ = a₃. Так, перехід з а₂ по z₂ в мінімізованому графові відбувається в стан а₃.

Аналогічно, в автоматі Мура S₄ стани а₄, а₈, а₆ ідентичні, стани а₇, a₉ також ідентичні. Облік цієї обставини приводить до мінімізованого графа автомата Мура S₄ (мал.17.11), в якому група станів замінюється станом з найменшим індексом, що входить до цієї групи.

мал.17.10. Мінімізований граф автомата Мілі S

мал.17.11. Мінімізований граф автомата Мура S4

Аналіз графа на мал.17.11 показує, що стани a₃ і а₅ також ідентичні і одне з них можна видалити, наприклад, стан а₅. Таким чином, мінімальний граф автомата S₄ ( мал.17.12) матиме тільки М = 5 станів.

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

мал.17.12. Мінімальний граф автомата Мура S₄

Размещено на Allbest.ru