Алгоритм є фундаментальною контрацепцією інформатики, і питання побудови автоматичних пристроїв, що реалізують за дане алгоритми, є одним із соснових питань проектування мікропроцесорних пристроїв відпрацювання інформації. Всі існуючі пристрої обробки інформації діляться на 2 большушій класу:
1) Функціональні перетворювачі
2) Автомати, в яких результат перетворення інформації, що надходить на вхід, залежить не тільки від того, яка інформація з'явилася на вході, а й від того, яка інформація надходила на ці автомати раніше. Такі пристрої називаються кінцевими автоматами або автоматами з пам'яттю (прикладами таких пристроїв є біологічні системи). На один і той же вхідний сигнал кінцевий автомат (КА) може реагувати по-різному, в залежності від того, в якому стані він знаходиться в даний момент.
При отриманні вхідного сигналу кінцевий автомат не тільки видає інформацію на вихід, як функцію цього стану, але і змінює свій стан, оскільки вхідний сигнал змінює його передісторію.
Число вхідних історій будь-якого кінцевого автомата нескінченно, але лічильно. Якщо автомат буде вести себе по-різному для кожної можливої передісторії, то він повинен мати нескінченний ресурс (пам'ять), щоб всі ці передісторії якось фіксувати. Якщо ввести на безлічі передісторій ---- то дві передісторії можна вважати еквівалентними, якщо вони однаковим чином впливають на подальшу поведінку автомата. Очевидно, що для свого функціонування автоматів досить запам'ятовувати клас еквівалентності, до якого належить передісторія. У разі, коли таких класів еквівалентності кінцеве число, є найпростішим, але саме така математична модель представляє велику практичну цінність і набула широкого поширення. Відповідна формальна модель і називається кінцевими автоматами.
Математичної моделі кінцевого автомата внутрішній стан автомата являє собою клас еквівалентності передісторій. Спрощено можна вважати, що внутрішній стан автомата це саме та його характеристика, яка однозначно визначає всі наступні реакції автомата на зовнішнє подія.
Кінцевий автомат - це пристрій, що працює в дискретні моменти часу (так звані такти). У кожному такому такті на вхід автомата подаються вхідні сигнали і на виході з'являється вихідний сигнал і відбувається зміна внутрішнього стану. Моменти спрацьовування (такти) визначаються або спеціальними тактується сигналами, або настанням зовнішнього події, яке полягає в тому, що на вхід автомата приходить новий вхідний сигнал. У цьому випадку вважається, що автомат управляється подіями і такти роботи автомата мають різну тривалість залежно від приходу зовнішніх сигналів.
Основні поняття і визначення кінцевих автоматів
Кінцевим автоматом (автоматом Міллі) називається математична модель, що складається з 5 елементів: (S, X, Y, # 948 ;, # 955;), де:
S - кінцеве безліч станів k>;
X - кінцевий вхідний алфавіт;
Y - кінцевий вихідний алфавіт;
Якщо в кінцевому автоматі виділено спеціальне початковий стан S0. то цей автомат називається ініціальним.
Два кінцевих автомата А1 і А2еквівалентни. якщо реалізовані ними відображення вхід-вихід - еквівалентні. Дві логічні функції f1 і f2 еквівалентні, якщо на всіх наборах аргументів вони мають однакові значення, тому що число аргументів логічної функції звичайно, то достатньо порівняти значення цих функцій на всіх наборах аргументів. Кінцевий автомат реалізує безліч вхідних послідовностей сигналів в кінцеве безліч вихідних сигналів, тому автоматні відображення вхід-> вихід, не можна визначити простим перерахуванням їх відображень і порівняти їх значення на всіх нескінченних множинах. Для того, щоб визначити еквівалентність автоматів необхідно розширити функції так, щоб функції переходів і виходів були визначені на множинах послідовностей сигналів вхідного алфавіту (послідовних ланцюжках) елементів х.
Визначення 2.3Пусть A =
(E - порожній ланцюжок, альфа - сама ланцюжок
Т.ч. розширені функції переходів і виходів визначені на множині вхідних послідовностей (вхідних ланцюжках) на відміну від звичайних функцій переходів і виходів, які визначені на множині вхідних сигналів.
Іншими словами, для даного автомата А і його функцій dА і Lа можуть бути визначені не тільки на безлічі X всіх його вхідних букв, але і на безлічі X * всіх вхідних слів. Для будь-якого вхідного слова
Це традиційне визначення з трьома крапками, набагато точніше і краще читається, ніж індуктивне визначення.
Функція переходів задається:
а) d (Si, aj) задається автоматної таблицею;
б) для будь-якого слова aÎX * і будь-яку літеру aj
За допомогою розширеної функції # 948; визначається (також індуктивно) розширена функція # 955; :
Зафіксуємо в автоматі А початковий стан S і кожному слову # 945; = aj aj. a поставимо у відповідність слово # 969; вихідному алфавіті У:
де Ù- операція конкатенації.
Це відповідність, що відображає вхідні слова в вихідні слова, називається автоматним відображенням, а також автоматним (або обмежено детермінованим) оператором. Якщо результатом застосування автоматного оператора до вхідному слову # 945; є вихідний слово # 969 ;, то це будемо позначати відповідно A (S, # 945;) = # 969; або A (# 945;) = # 969 ;, причому | # 945; | = | # 969; | або l (# 945;) = l (# 969;), тобто слова # 945; і # 969; мають однакову довжину.
Автоматне відображення володіє двома властивостями, які безпосередньо випливають з (2-5): слова a і w мають однакову довжину (властивість збереження довжини) і, крім того, автоматні оператори - це оператори без передбачення, тобто оператори, які, переробляючи слово зліва направо, не заглядають вперед. Це властивість відображає той факт, що i-тая буква вихідного слова залежить тільки від перших i букв вхідного слова.
Визначення 2.4 Нехай А =
Визначення 2.5 Автомат А називається сильно зв'язковим. якщо з будь-якого його стану можна досягти будь-яке інше стан.
Визначення 2.6 Автомат називається автономним. якщо його вхідний алфавіт складається з однієї літери X =.
Визначення 2.7 Автомат називається частковим або не повністю визначеним. якщо хоча б одна з двох функцій не повністю визначена. В такому автоматі для деяких пар (стан - вхід, стан - вихід) значення функцій # 948; або # 955; не визначені. У автоматної таблиці неповна визначеність автомата виражається в тому, що деякі її клітини не заповнені.
Визначення 2.8 Кінцеві автомати А = і B = називаються еквівалентними. якщо виконані дві умови:
а) їх вхідні алфавіти збігаються X = X = X;
б) реалізовані ними відображення збігаються: ( # 945;ÎX) # 955; (S. # 945;) = # 955; (S, # 945;).
Однак відповісти на питання, еквівалентні чи автомати, перебором їх реакцій на все вхідні ланцюжка неможливо, тому що їх нескінченно багато, тому проблема еквівалентності КА не є тривіальною. Метод вирішення цього завдання заснований на понятті прямого твори автоматів.
Визначення 2.9 Прямим твором кінцевих автоматів А = і B = з однаковим вхідним алфавітом X (позначається AxB) називається автомат:
AxB =, де
а) (S Î S) (S Î S) (x ÎX) # 948; ((S, S), x) = (# 948; (S, x), # 948; (S, x));
б) (S Î S) (S ÎS) (x ÎX) # 955; ((S, S), x) = (# 955; (S, x), # 955; (S, x)).
Іншими словами, кінцевий автомат, що є прямим добутком двох КА, в якості своїх станів має пари станів, вихідних автоматів, його початковий стан є пара їх початкових станів, вихідний алфавіт - безліч пар вихідних символів автоматів - множників, а функції переходів і виходів визначені покомпонентно . Т.ч. пряме твір КА - це просто два що стоять поруч невзаимодействующих КА, синхронно працюють на одному загальному вході
14.Способи завдання кінцевих автоматів.
Пристрій, що оперують з логічними сигналами, що приймає тільки 2 значення - 0 і 1 і має деяку безліч внутрішніх еквівалентних станів S, безліч вхідних сигналом x і безліч вихідних сигналів y - називається цифровим автоматом.
Найпростішим цифровим автоматом є будь-комбінаційний пристрій, що має єдине внутрішній стан. У цьому пристрої кожного набору вхідних логічних змінних відповідає деякий вихідний сигнал. Якщо автомат може знаходиться в декількох еквівалентних внутрішніх станах, то його реакція на вхідні сигнали визначається не тільки поточним набором вхідних сигналів, а й внутрішнім станом автомата.
Передбачається, що зміни вхідних сигналів і внутрішніх станів відбувається миттєво, тому автомат працює в дискретному часі Ti, де протяжність кожного такту (інтервалу) може бути як завгодно великий.
Якщо протягом часу не відбулося змін вхідних сигналів x і відповідно внутрішніх станів S.
Розрізняють автомати Мура і автомати Міллі.
Автомат Мура є окремим випадком більш широкого поняття - автомата Мілі.
Автомати Мура описуються наступними функціями переходів і виходів:
Кожне нове стан автомата Мура обумовлено попереднім станом і вхідним сигналом, а вихідна функція - в кожен даний момент часу однозначно визначається станом автомата.
Автомати Мілі відрізняються від автоматів Мура тим, що вихідний сигнал в цьому автоматі залежить не тільки від стану, але і від вхідного сигналу.
Si + 1 = f (Si, xi + 1) yi + 1 = y (si, xi + 1)
Поняття внутрішнього стану автомата передбачає наявність у автомата внутрішньої пам'яті. Число різних еквівалентних станів залежить від глибини пам'яті.
Як елементи пам'яті можуть використовуватися стандартні модулі ПЗУ або логічні схеми з зворотними зв'язками зокрема - різні типи тригерів.
В принципі будь-який автомат Мура можна звести до автомату Мілі і навпаки.
Автомат Мілі - більш універсальний пристрій
У автомата Мілі немає таких обмежень, які є у Мура
Задавши безліч (x s y) досить важко визначити як працює кінцевий автомат. Наведені вище рівняння, що описують функціонування автоматів мура і милі встановлюють зв'язок між множинами x s y, але вони незручні для опису функціонування конкретних автоматів, тому на практиці набули поширення інші способи опису роботи кінцевих автоматів.
Найбільш широко поширені табличное завдання, де задані таблиці переходів і виходів кінцевого автомата. Будівля кінцевого у вигляді граф-схеми, а так само завдання кінцевих автоматів у вигляді ЛГСА (логічна схема алгоритмів).
Розглянемо завдання КА, який для будь-якої пари чисел, записаних в двійковій системі числення обчислює і виводить їх суму, при цьому дані починаються з бітів, які мають найменші розряди і числа читаються справа-наліво.
(В квитках буде приклад з тригерами, RS і інші)
У таблиці 2.1 можливі стани у вигляді впорядкованої послідовності записані в 1ой рядку.
Вхідні сигнали в упорядкованому вигляді записані в першому стовпці.
На перетині рядків і стовпців отримуємо клітку в якій записано новий стан.
Таблиця переходів (2.1) може бути визначена неповністю. В цьому випадку в таблиці є прочерки в окремих клітках.
Деякі сигнали не викликають зміни стану. Так, під дією вхідних сигналів 0 і 1автомат зберігає стан S0, Якщо він в ньому знаходився і стан S1, якщо при подачі такої комбінації вхідних сигналів він перебував в стані S1.
Безліч вихідних сигналів подібним чином задається для кожної пари Si, Lj і на перетині соответствтвующей рядки і стовпці отримуємо вихідний сигнал автомата.
Значення вихідного сиг налу автомата наведено в таблиці 2.2
Іноді, якщо є така можливість - обидві таблиці суміщають.
Для автомата Мура таблиця виходів вироджується в один рядок, яку можна записати в першому рядку таблиці переходів.
Табличне опис служить зручним формалізованою мовою, на якому можна задати будь-який кінцевий автомат, що дає взаєморозуміння між замовником і розробником.
Поширений засіб опису автомата - логічна граф-схема опису алгоритму.
15. Кінцевий автомат як модель «реагує системи».
Останнім часом для програмістів, які працюють в галузі інформатики, стала зрозумілою необхідність виділення особливого класу систем, який був названий реагують системами. Ці системи здатні реагувати на потік зовнішніх подій. Виявилося, що математична модель кінцевого автомата є зручним засобом опису таких систем. Зручність застосування математичної моделі кінцевого автомата полягає в тому, що ця модель має ясністю семантики, наочністю і виразністю і в той же час вона досить сувора і формальна.
Однак виявилося, що класична математична модель кінцевого автомата має ряд недоліків. Головним недоліком такої моделі є відсутність засобів вираження ієрархії стану, а також математичного апарату для відображення переривань і продовження нормальної роботи системи після обробки переривання.
Простим і досить ефективним розширенням моделі класичного кінцевого автомата є введення поняття «зовнішня подія», наступ якого можна вважати умовою переходу автомата в новий стан. Такими подіями можна вважати отримання сигналу на вхід автомата, переривання і спрацьовування таймера. З спрацьовуванням таймера природно зв'язується поняття часу в автоматі. Дійсно, введенням поняття часу в кінцевому автоматі можна пов'язати з обмеженням перебування автомата в заздалегідь заданому, конкретному стані. Таке обмеження, якщо воно необхідне, найкраще ставити таймером математичної моделі кінцевого автомата, спрацьовування таймера повинно викликати перехід автомата в інший стан. Розглянемо як приклад специфікацію процесу, що визначає одинарний або подвійне клацання миші. Нагадаємо, що подвійним клацанням вважається послідовність з 2-х натискань клавіші, колективна проміжком часу t = 250мс. Уявімо граф переходів кінцевого автомата, вирішального цю задачу.
По першому клацанням миші (клік) автомат переходить зі стану S0 в стан S1, і якщо до закінчення наступних t = 250мс на вхід надходить ще один сигнал (подія клік), то на вихід буде виданий сигнал click \ double в іншому випадку t \ click . У будь-якому з цих варіантів автомат повертається в положення S0 і робота автомата повторюється.
16. Кінцевий автомат як модель протоколу передачі повідомлень в мережах.