Квиток№ 1
ВизначенняЦА. Основні поняття теорії автоматів: ЦА кінцеві, синхронні, асинхронні,ідеалізовані, абстрактні, структурні. Абстрактна і структурна теоріяавтоматів.
ЦА- Пристрій, призначений для перетворення цифрової інформації, здатнепереходити під впливом вхідних сигналів з одного стану в інший івидавати вихідні сигнали.
ЦАкінцеві , коли безліч вхідних івихідних сигналів, а також число вхідних і вихідних каналів і безлічстанів автомата кінцеві.
СинхроннийЦА - вхідні сигнали діють встрого певні моменти часу при Т = конст, що визначаються генераторомсинхронізуючих імпульсів, в які можливий перехід автомата з одногостану в інший.
АсинхроннийЦА - Т <> конст та визначаєтьсямоментами надходження вхідних сигналів, а перехід автомата з одного станув інше здійснюється при незмінному стані входу.
ІдеалізованийЦА - Не враховуються перехідніпроцеси в елементах схеми автомата, різниця у фактичних величинах Т для правильногофункціонування автомата не має значення, тому для опису законівфункціонування ЦА вводять абстрактне час, що приймає цілі невід'ємнізначення.
АбстрактнийЦА - шестікомпонентний вектор S = {A, z, w, Пѓ, О», a1},у якого: А-безліч станів автомата, Z - вхідні сигнали, W-вихіднісигнали, Пѓ-функція переходів, О»-функціявиходів, а1 - початковий стан автомата.
СтруктурнийЦА - враховує структуру вхідних івихідних сигналів, а також його внутрішній устрій на рівні структурнихсхем.
Структурнатеорія ЦА вивчає загальні прийомипобудови структурних схем автоматів на основі елементарних автоматів.
Абстрактнатеорія ЦА - вивчаються найбільш загальнізакони їх поведінки без урахування кінцевої структури автомата і фізичної природиінформації.
Квиток№ 2
ВаріантиЦА: автомати Мілі і Мура, С-автомат, автомат без пам'яті, автономний автомат,автомат без виходу, керуючі та операційні автомати, мікропрограмніавтомати.
Автомат Милі - a (t +1) = Пѓ (a (t), z (t)); w (t ) =О» (a (t), z (t)); a (0) = a1, t = 0,1,2, ...
Автомат Мура - a (t +1) = Пѓ (a (t), z (t)); w (t ) =О» (a (t)); a (0) = a1, t = 0,1,2, ...
С-автомат : під абстрактним С-автоматом розуміють математичнумодель цифрового пристрою, обумовлену восьмікомпонентним вектором S = {A, Z, W, U, Пѓ, О»1,О»2, a1}, де А-безліч станів, Z-вхідний алфавіт, W-вихідний алфавіт автомата Мілі, U-вихідний алфавіт автомата Мура, Пѓ-функція переходів автомата, О»1-функціявиходів автомата Мілі, О»2-функція виходів автомата Мура, а1 - початковестан.
Автоматбез пам'яті (КС) : Алфавіт станівтакого автомата містить єдину букву, тому поняття функції переходіввироджується і стає непотрібним для опису роботи автомата, тобто вихіднийсигнал в даному такті залежить тільки від вхідного сигналу того ж такту і ніякне залежить від раніше прийнятих сигналів.
Автономнийавтомат : У такому автоматі вхіднийалфавіт складається з однієї літери. Автомат задається чотирма об'єктами: А, W, Пѓ,О» з можливим виділенням початкового стану а1. Якщоавтомат скінченний і число його станів одно до, то серед значень а (1), А (2), ...,а (к) знайдуться повторювані стану. АА використовуються для побудовигенераторів періодичних послідовностей, генераторів сінхросерій і вінших задаючих пристроях.
Автоматбез виходу : У такому автоматі вихіднийалфавіт містить тільки одну букву. Автомат задається трьома об'єктами: А, Z, Пѓ.З функцій, задаючих поведінку автомата, зберігається лише функція переходів.
Керуючіі операційні автомати : ОАреалізує дії над вихідною інформацією (словами), тобто євиконавчою частиною операційного пристрою, а УА управляє роботою ОА, тобтовиробляє необхідні послідовності керуючих сигналів вВідповідно до алгоритму виконуваної операції. УА використовуються не тільки вопераційних пристроях обчислювальної техніки в системі УА-ОА, але і врізноманітних системах автоматики з управління технологічними процесами іоб'єктами.
Мікропрограмніавтомати : Алгоритм записуваний здопомогою мікрооперацій і логічних умов, називається мікропрограмою.
Квиток№ 3
АвтоматиМилі та Мура. З-автомат. Закони функціонування. Основні відмінності.
Автомат Милі - a (t +1) = Пѓ (a (t), z (t)); w (t ) =О» (a (t), z (t)); a (0) = a1, t = 0,1,2, ...
Автомат Мура - a (t +1) = Пѓ (a (t), z (t)); w (t ) = О»(A (t)); a (0) = a1, t = 0,1,2, ...
Ціавтомати розрізняються способом визначення вихідного сигналу. В автоматі Міліфункція О» визначає вихідний сигнал в залежності від стануавтомата і вхідного сигналу в момент часу t, а в автоматіМура накладаються обмеження на функцію О»,полягають у тому, що вихідний сигнал залежить тільки від стану автомата іне залежить від значення вхідних сигналів. Вихідні сигнали ЦА Мура відстають наодин такт від вихідних сигналів ЦА Мілі, еквівалентного йому.
С-автомат : під абстрактним С-автоматом розуміють математичнумодель цифрового пристрою, обумовлену восьмікомпонентним вектором S = {A, Z, W, U, Пѓ, О»1,О»2, a1}, де А-безліч станів, Z-вхідний алфавіт, W-вихідний алфавіт автомата Мілі, U-вихідний алфавіт автомата Мура, Пѓ-функція переходів автомата, О»1-функціявиходів автомата Мілі, О»2-функція виходів автомата Мура, а1 - початковестан.
a (t +1) = Пѓ (a (t), z (t)); w (t) = О» 1 (a (t),z (t)); u (t) = О» (a (t)); a (0) = a1, t = 0,1,2, ...
ВідмінністьЗ-автомата в тому, що він одночасно реалізує дві функції виходів О»1і О»2, кожна з яких характерна для моделі Мілі імоделі Мура окремо. Від С-автомата легко перейти до автоматів Мілі і Мураз урахуванням можливих зрушень вихідних сигналів на такт, аналогічно тому, якможливий перехід від автомата Мілі до автомата Мура і навпаки. Багато реальнихавтоматів працює по моделі С-автомата.
Квиток№ 4
Системиканонічних рівнянь (СКУ) та системи вихідних функцій (СВФ). Побудова СКУІ СВФ для автоматів Мілі і Мура.
СКУі СВФ є аналітичною інтерпретацією таблиць переходів і виходів абографів ЦА. СКУ визначає функції переходів ЦА, а СВФ визначає функціївиходів ЦА.
Кожнестан ЦА інтерпретується як подія, відповідне безлічі переходівв цей стан: As (t +1) = v Zf (t) & Am (t).Для скорочення запису СКУ та СВФ опускають знаки кон'юнкції і часу t в правій частині рівняння.
Для автомата Милі : СКЗ: a1 (t +1) = a1z1 v a2z2 v a4z2; a2 (t +1) =a1z2; a3 (t +1) = a3z1 v a4z2; a4 (t +1) = a2z1 v a3z2
CВФ: w1 (t) = a1z1 v a1z2; w2 (t) = a2z2; w3 (t)= A3z1 v a4z2; w4 (t) = a4z1; w5 (t) = a4z1 v a3z2
Для автомата Мура : a1 (t +1) = a2z1 v a3z1; a2 (t +1) = a4z2;a3 (t +1) = a6z1; a4 (t +1) = a3z2 v a2z2 v a1z2; a5 (t +1) = a5z1 v a6z2; a6 (t +1) =a4z1 v a5z2
СВФ: w1 (t) = a1 v a4; w2 (t) = a1; w3 (t) = a5;w4 (t) = a3; w5 (t) = a6
Квиток№ 5
ЗавданняЦА на стандартних мовах: таблиці, графи і їх аналітична інтерпретація - СКУі СВФ. Умови однозначності і повної визначеності.
Стандартні(Автоматні) мови задають функції переходів і виходів в явному вигляді. Для того,щоб задати автомат, необхідно описати все компоненти вектора S = {A, z, w, Пѓ, О», a1}.
Табличнийспосіб : автомат Мілі описується за допомогою двох таблиць: таблиці переходів і таблиці виходів. Таблицяпереходів задає функцію Пѓ, таблиця виходів - О». Кожномустовпцю таблиці поставлено у відповідність один стан з безлічі А, кожнійрядку - один вхідний сигнал з безлічі Z. Наперетині рядка і стовпця в таблиці переходів, записується стан as, вяке має перейти автомат з стану am, піддією вхідного сигналу zf, тобт...
