Федеральне агентство з освіти
Сибірська державна автомобільно-дорожня академія (СібАДІ)
Факультет: Інформаційні системи в управлінні
Спеціальність: 090103 Інформаційна безпека АС
Кафедра: Інформаційна безпека
Курсова робота
з дисципліни Кінцеві автомати
Тема роботи: «Еквівалентність та мінімізація кінцевих автоматів»
Виконав: студент гр. БІ - 11І1
Галкін Кирило Андрійович
Омськ - 2014
Зміст
Введення
1. Теоретична частина
1.1 Визначення автоматів Мілі та Мура
1.2 Еквівалентність кінцевих автоматів
1.3 Мінімізація кінцевого автомата
2. Практична частина
Висновок
Список літератури
Введення
У цій роботі будуть розглянуті основні поняття кінцевих автоматів, а також їх еквівалентності та мінімізації. Буде виконано докладний рішення декількох типових завдань для докладного вивчення алгоритмів мінімізації кінцевих автоматів Мілі та Мура.
Мета роботи:
. Ознайомитися з теоретичними основами кінцевих автоматів-распознавателей;
. Уявити кілька прикладів побудови кінцевих автоматів, які розпізнають деякі мови.
1. Теоретична частина
Кінцеві автомати [1] є математичною моделлю пристроїв, переробних дискретну вхідну інформацію в режимі реального часу raquo ;, тобто в темпі її надходження (рис.1).
Малюнок 1 - Автомат
На такі пристрої в послідовні дискретні моменти часу 1,2, ..., t, t + 1, ... надходять вхідні сигнали x (1), x (2), ..., x (t), x (t + 1), ... і у відповідь на них автомат A виробляє вихідні сигнали y (1) y (2), ..., y (t), y (t + 1),.... Кінцеві автомати характеризуються двома особливостями:
1. Відсутність передбачення: вихідний сигнал y (t), що видається автоматом в момент t, залежить лише від отриманих до цього часу входів x (1), x (2), ..., x (t), тобто автомат не може передбачити майбутні входи і заздалегідь на них відреагувати. Таким чином, є деяка функція виходів? (X (1), x (2), ..., x (t))=y (t), що визначає черговий вихід за попереднім входу.
. Кінцева пам'ять: у кожен момент t інформація в автоматі про отриманий до цього моменту вході x (1), x (2), ..., x (t) кінцева. Ця властивість зручно інтерпретувати наступним чином: автомат має кінцеве безліч станів S і в кожний момент знаходиться в одному з цих станів. При отриманні чергового входу стан може змінитися. Таким чином, стан q? S, в якому знаходиться автомат після отримання вхідної послідовності x (1), x (2), ..., x (t), і являє інформацію про цю послідовності, використовувану в подальшій роботі автомата при визначенні наступного стану і виходу.
1.1 Визначення автоматів Мілі та Мура
Визначення 1. Кінцевим автоматом Мілі (рис.2) [2] називається шістка об'єктів: А= lt; S, X, Y, s 0,? ,? gt ;, де
· S - кінцеве непорожнє безліч (станів);
· X - кінцеве непорожнє безліч вхідних сигналів (вхідний алфавіт);
· Y - кінцеве непорожнє безліч вихідних сигналів (вихідний алфавіт);
· s 0 - початковий стан;
·?:S? X ® S - функція переходів;
·?:S? X ® Y - функція виходів.
Для побудови графа автомата Мілі (рис.2) нам необхідно позначити його стану у вигляді вершин графа, а переходи і виходи - ребрами.
Малюнок 2 - Графічне представлення автомата Мілі
Крім графічного способу (рис.2) відображення для автомата можна використовувати і табличне (табл.1), задаючи функції переходів і виходів у вигляді таблиць.
Таблиця 1 - Табличне представлення автомата Мілі (таблиці переходів і виходів)
? 012s0s1s2s3 s1s1s0s0 s2s2s1s3s3s3s3s2? 012s0y1y2y3 s1y1 y0y3s2y1 y2y3s3y1 y2 y3
Визначення 2. Кінцевим автоматом Мура (рис.3) називається шістка об'єктів А= lt; S, X, Y, s 0,? ,? gt ;, де:
· S - безліч станів;
· X - вхідний алфавіт;
· Y - вихідний алфавіт;
