МІНІСТЕРСТВО ОСВІТИ І НАУКИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" ВИВЧЕННЯ МЕТОДІВ АНАЛІЗУ ТА СИНТЕЗУ СКІНЧЕННИХ АВТОМАТІВ МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 5 з курсу «Схемотехніка пристроїв технічного захисту інформації» для студентів базового напряму 6.170102 «Системи технічного захисту інформації» Затверджено на засіданні кафедри «Захист інформації» Протокол № 12 від 07.05.2015р. Львів – 2015  Мета роботи: вивчення методів аналізу і синтезу скінченних автоматів. 1. ОСНОВНІ ВІДОМОСТІ Цифровий автомат - це пристрій, що здійснює прийом, зберігання і перетворення дискретної інформації за деяким алгоритмом. Загальну теорію автоматів ділять на абстрактну і структурну. Абстрактна теорія, абстрагуючись від структури автомата (тобто не цікавлячись способом його побудови), вивчає тільки поведінку автомата відносно зовнішнього середовища. Структурна теорія цікавиться як структурою самого автомата, так і структурою вхідних дій і реакцією на них автомата. В структурній теорії вивчаються способи побудови автоматів, способи кодування вхідних дій і реакцій на них автомата. 1.1. Абстрактні цифрові автомати. Основні поняття Абстрактний цифровий автомат з пам’яттю А задається сукупністю п’яти об’єктів:
, де
,
- множина абстрактних вхідних сигналів автомата А (вхідний алфавіт автомата А);
,
- множина абстрактних станів автомата А (алфавіт станів автомата А);
,
- множина абстрактних вихідних сигналів автомата А (вихідний алфавіт автомата А);
- функція переходів автомата А - визначає стан автомата
в такті
в залежності від стану автомата
і від значення вхідної букви
на
- ому такті:
, (1)(
- дискретні моменти часу);
- функція виходів автомата А - визначає значення вихідної букви
на
- ому такті в залежності від стану автомата
і від вхідної букви
на тому ж
- ому такті:
(2) На множині Z як правило фіксується один із станів
як початковий. Зауваження: Поняття стану у визначенні абстрактного автомата введено в зв’язку з тим, що більшість реальних процесів, якими керують цифрові автомати, вимагають для свого правильного протікання знання передісторії розвитку процесу в часі. Іншими словами вихідний сигнал, що видається автоматом в деякий момент часу, визначається не тільки вхідною дією на автомат (командою), але й станом, в якому автомат перебував в попередній момент часу. Наприклад, якщо потрібно побудувати автомат керування переключенням світлофору при умові, що на вхід автомата надходить тільки один абстрактний вхідний сигнал «переключити світлофор», то в кожен момент часу для організації правильної роботи автомату, крім згаданого вхідного сигналу, потрібно мати також інформацію про попередній стан світлофора. Букви
- це не є в загальному випадку двійкові (або інші цифрові) змінні. Це абстрактне значення відповідно вхідної інформації, стану автомата і вихідної інформації, які відрізняються від всіх інших можливих значень. Вже на рівні структурної теорії кожну з цих букв можна закодувати певною кількістю цифрових (наприклад двійкових) змінних. Наприклад, на рівні абстрактної теорії деяка абстрактна вхідна буква
може мати значення «збільшити швидкість в 2 рази», а на рівні структурної теорії ця абстрактна буква
може бути закодована двома структурними двійковими змінними
і мати значення 10: (
,
). Загалом, абстрактний автомат реалізує відображення множини букв вхідного в множину букв вихідного алфавітів і має тільки один вхідний і один вихідний канали, а отже є лише математичною моделлю реального процесу. Функція виходів автомата
може бути двох типів. Якщо вихідний сигнал автомата визначається виразом (2), тобто залежить як від стану автомата, так і від вхідного сигналу, то пристрій називають автоматом Мілі. Якщо ж вихідний сигнал не залежить від вхідного, а однозначно визначається станом автомата:
, (3)то пристрій називають автоматом Мура. Є різні способи задання функцій виходів
і переходів
. В цій роботі ми будемо користуватися табличним способ...