Задачі
Визначити, чи є асинхронним автомат Мура, заданий на рис. 5.3.а, якщо ні, то який максимальний підавтомат таким є.
Визначити, чи є асинхронними автомати Мілі, задані:
на рисунку 5.1.;
у табл. 5.1.;
на рисунку 5.2.;
на рисунку 5.3.б;
на рисунку 5.4..
Побудувати асинхронний тактуємий автомат, що описує дії ліфта в триповерховому будинку. Три стани ліфта відповідають його перебуванню на поверхах, входами є кнопки на поверхах, а також сигнал про те, що жодна з кнопок не натиснута. Виходами є сигнали, що визначають рух нагору, вниз і зупинку. Передбачається, що одночасно може бути натиснута тільки одна кнопка і до досягнення ліфтом потрібного поверху вхід не змінюється.
Побудувати асинхроний тактуємий автомат для ліфта задачі 2 з умовою - при відсутності команд ліфт повертається на перший поверх.
Побудувати асинхроний тактуемий автомат для ліфта, описаного в задачі 3, за умови, що всі команди (натискання кнопок) повинні запам'ятовуватися і відповідно до порядку натискання виконуватися.
Перетворення автоматів Мілі і Мура
Задачі
Перетворити автомат Мура (табл. 5.2.) в автомат Мілі. Побудувати відсутні таблицю переходів-виходів, графи і матриці з'єднань.
Таблиця 5.2
| S X Y | S1 y1 | s2 y2 | s3 y1 |
| x1 | S2 | s1 | s3 |
| x2 | S1 | s3 | s2 |
| x3 | S3 | s3 | s1 |
Перетворити автомат Мілі (табл. 5.3.) в автомат Мура. Побудувати відсутні таблицю переходів-виходів, графи і матриці з'єднань.
Таблиця 5.3
| S X | s1 | s2 | S3 |
| x1 | s2/y1 | S1/y1 | s3/y2 |
| x2 | s1/y2 | S3/y1 | s2/y2 |
| x3 | s3/y2 | S3/y2 | s1/y1 |
Довести чи спростувати можливість перетворення:
автомата Мура (рис. 5.3.а) в автомат Мілі (рис. 5.3.б);
автомата Мілі (рис. 5.3.б) в автомат Мура (рис. 5.3.а);
автомата Мілі (табл. 5.4.) в автомат Мура (табл. 5.5.);
автомата Мура (табл. 5.5.) в автомат Мілі (табл. 5.4.).
Таблиця 5.4
| S X | s1 | s2 | s3 |
| x1 | s2/y1 | S1/y1 | s3/y2 |
| x2 | s1/y2 | S3/y2 | s2/y1 |
| x3 | s3/y2 | S3/y2 | s1/y1 |
Таблиця 5.5
| S X Y | s1 y1 | s2 y1 | s3 y2 | s4 y2 |
| X1 | s2 | S1 | s3 | s2 |
| X2 | s1 | S3 | s2 | s1 |
| X3 | s3 | S3 | s1 | s3 |
Сполучена модель автоматів – С-автомат
Задачі
Побудувати С-автомат для автоматів Мілі і Мура (табл. 5.4, 5.6.).
Таблиця 5.6
| S X Y | S1 y1 | s2 y1 | s3 y2 |
| X1 | S2 | s1 | s3 |
| X2 | S1 | s3 | s2 |
| X3 | S3 | s3 | s1 |
Побудувати С-автомат для автоматів Мілі і Мура (табл. 5.4., 5.5.).
Побудувати С-автомат для автоматів Мілі і Мура, заданих за допомогою «зважених» множин фактор-безлічей, де для станів Мілі задаються трійки – ((вхід, вихід), новий стан), для станів Мура задаються вихідні мітки станів і двійки – ((вихід), (вхід, новий стан)):
Мілі – ({((x1, y1), s2), ((x2, y1), s3), ((x3, y1), s2)}, {((x1, y2), s1), ((x2, y2), s2), ((x3, y1), s1)}, {((x1, y1), s3), ((x2, y2), s3), ((x3, y1), s1)}),
Мура – ((y2, y1, y2), ({(x1, s2), (x2, s3), (x3, s2)}, {(x1, s1), (x2, s2), (x3, s1)}, {(x1, s3), (x2, s3), (x3, s1)}));
Мілі – ({((x1, y2), s1), ((x2, y1), s2), ((x3, y2), s2)}, {((x1, y1), s2), ((x2, y1), s2), ((x3, y1), s3)}, {((x1, y2), s3), ((x2, y2), s1), ((x3, y2), s2)}),
Мура – ((y1, y1, y2), ({(x1, s1), (x2, s3), (x3, s1)}, {(x1, s2), (x2, s2), (x3, s1)}, {(x1, s3), (x2, s1), (x3, s3)}));
Мілі – ({((x1, y1), s2), ((x2, y1), s3), ((x3, y2), s1)}, {((x1, y2), s3), ((x2, y1), s3), ((x3, y2), s1)}, {((x1, y1), s3), ((x2, y2), s3), ((x3, y1), s2)}),
Мура – ((y2, y2, y1), ({(x1, s3), (x2, s2), (x3, s1)}, {(x1, s2), (x2, s2), (x3, s3)}, {(x1, s1), (x2, s3), (x3, s2)})).
Композиція автоматів
Задачі
Для автоматів Мілі (табл. 5.7., 5.8.) побудувати рівнобіжне з'єднання.
Таблиця 5.7
| S X | s11 | s12 |
| x11 | s12/y11 | s11/y11 |
| x12 | s11/y12 | s11/y11 |
Таблиця 5.8
| S X | s21 | s21 |
| x21 | s21/y21 | s22/y22 |
| x22 | s21/y21 | s21/y21 |
Для двох автоматів Мілі, заданих за допомогою «зважених» множин фактор-безлічей, побудувати рівнобіжне з'єднання:
Мілі1 – ({((x11, y11), s12), ((x12, y11), s13)}, {((x11, y12), s11), ((x12, y12), s12)}, {((x11, y11), s13), ((x12, y12), s13)}), Мілі2 – ({((x21, y22), s21), ((x22, y21), s22)}, {((x21, y22), s21), ((x22, y22), s22)}, {((x21, y21), s21), ((x22, y22), s22)});
Мілі1 – ({((x11, y12), s11), ((x12, y11), s13)}, {((x11, y11), s12), ((x12, y12), s12)}, {((x11, y12), s12), ((x12, y11), s13)}), Мілі2 – ({((x21, y21), s22), ((x22, y21), s21)}, {((x21, y21), s21), ((x22, y22), s21)}, {((x21, y22), s22), ((x22, y21), s21)}).
Для двох автоматів Мілі, заданих за допомогою таблиць переходів-виходів (табл. 5.9., 5.10.), побудувати послідовне з'єднання за умови, що вхідний алфавіт першого автомата Мілі X дорівнює вхідному алфавіту композиції, вихідний алфавіт композиції дорівнює вихідному алфавіту другого автомата Z і вхідний алфавіт другого автомата дорівнює вихідному алфавіту першого автомата Y.
Таблиця 5.9
| S X | s11 | s12 | S13 |
| X11 | s12/y1 | s11/y1 | s13/y2 |
| X12 | s11/y2 | s13/y1 | s12/y1 |
Таблиця 5.10
| S X | s21 | s22 | s23 |
| y1 | s22/z1 | s21/z1 | s23/z2 |
| y2 | s21/z2 | s23/z2 | s22/z1 |
Для двох автоматів Мілі, заданих за допомогою «зважених» множин фактор-безлічей, побудувати послідовне з'єднання за умови, що вхідний алфавіт першого автомата Мілі X дорівнює вхідному алфавіту композиції, вихідний алфавіт композиції дорівнює вихідному алфавіту другого автомата Z і вхідний алфавіт другого автомата дорівнює вихідному алфавіту першого автомата Y:
Мілі1 – ({((x1, y1), s12), ((x2, y1), s13)}, {((x1, y2), s11), ((x2, y2), s12)}, {((x1, y1), s13), ((x2, y2), s13)}), Мілі2 – ({((y1, z2), s21), ((y2, z1), s22)}, {((y1, z2), s21), ((y2, z2), s22)}, {((y1, z1), s21), ((y2, z2), s22)});
Мілі1 – ({((x1, y2), s11), ((x2, y1), s13)}, {((x1, y1), s12), ((x2, y2), s12)}, {((x1, y2), s12), ((x2, y1), s13)}), Мілі2 – ({((y1, z1), s22), ((y2, z1), s21)}, {((y1, z1), s21), ((y2, z2), s21)}, {((y1, z2), s22), ((y2, z1), s21)}).
Для автомата Мілі й автомата Мура, заданих за допомогою таблиць переходів-виходів (табл. 5.11., 5.12.), побудувати з'єднання зі зворотним зв'язком за умови, що вхідний алфавіт автомата Мілі дорівнює декартовому добутку вихідного алфавіту автомата Мура Z і вхідного алфавіту композиції Х, вихідний алфавіт композиції дорівнює вихідному алфавіту автомата Мура Z і вхідний алфавіт автомата Мура дорівнює вихідному алфавіту автомата Мілі Y.
Таблиця 5.11
| S Z´X | s11 | s12 | s13 |
| (z1,x1) | s12/y1 | s11/y1 | s13/y2 |
| (z1,x2) | s11/y2 | s13/y1 | s12/y1 |
| (z2,x1) | s13/y2 | s12/y2 | s11/y1 |
| (z2,x2) | s12/y1 | s11/y2 | s13/y1 |
Таблиця 5.12
| S Y Z | s21 z1 | s22 z1 | s23 z2 |
| y1 | s22 | s21 | s23 |
| y2 | s21 | s23 | s22 |
Для автомата Мілі й автомата Мура, заданих за допомогою «зважених» множин фактор-безлічей, побудувати з'єднання зі зворотним зв'язком за умови, що вхідний алфавіт автомата Мілі дорівнює декартовому добутку вихідного алфавіту автомата Мура Z і вхідного алфавіту композиції Х, вихідний алфавіт композиції дорівнює вихідному алфавіту автомата Мура Z і вхідний алфавіт автомата Мура дорівнює вихідному алфавіту автомата Мілі Y:
Мілі – ({(((z1, x1), y1), s12), (((z1, x2), y1), s13), (((z2, x1), y2), s11), (((z2, x2), y1), s13)}, {(((z1, x1), y2), s11), (((z1, x2), y2), s12), (((z2, x1), y2), s13), (((z2, x2), y1), s12)}, {(((z1, x1), y1), s13), (((z1, x2), y2), s13), (((z2, x1), y1), s11), (((z2, x2), y2), s13)}), Мура – ((z2, z1), {(y1, s21), (y2, s22)}, {(y1, s22), (y2, s21)});
Мілі – ({(((z1, x1), y2), s11), (((z1, x2), y1), s13), (((z2, x1), y1), s12), (((z2, x2), y1), s12)}, {(((z1, x1), y1), s12), (((z1, x2), y2), s12), (((z2, x1), y2), s13), (((z2, x2), y2), s13)}, {(((z1, x1), y2), s12), (((z1, x2), y1), s13)}, (((z2, x1), y1), s12), (((z2, x2), y1), s12)), Мура – ((z1, z2), {(y1, s22), (y2, s21)}, {(y1, s21), (y2, s21)}).
СПИСОК ЛІТЕРАТУРИ
Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математика в примерах и задачах. – К.: УМК ВО, 1992.
Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программирование. – К.:Наук.думка, 1989.
Кук Д., Бейз Г. Компьютерная математика. – М.:Наука, 1990.
Горбатов В.А. Основы дискретной математики. – М.:Высш.шк., 1986.
Емеличев В.А., Мельников Д.И. и др. Лекции по теории графов. – М.:Наука, 1990.
Брауэр В. Введение в теорию конечных автоматов. – М.:Радио и связь, 1987.
Сигорский В.П. Математический аппарат инженера. – К.:Техника, 1975.
Коршунов Ю.М. Математические основы кибернетики. – М.:Энергия, 1980.
Яблонский С.В. Введение в дискретную математику. – М.:Наука, 1979.
Лапа В.Г. Математические основы кибернетики. – К.:Вища шк., 1974.
Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.:Мир, 1976.
Зыков А.А. Основы теории графов. – М.:Наука, 1987.
Кристофидес Н. Теория графов. Алгоритмический подход. – М.:Мир, 1978.
Глушков В.М. Синтез цифровых автоматов. – М.:Физматиздат, 1962.
Мелихов А.Н. Ориентированные графы и конечные автоматы. -М.:Наука, 1971.
Методические указания и задачи к практическим занятиям по курсам "Дискретная математика" и "Теоретические основы кибернетики". /Сост.: Ф.С. Шапо, В.А. Бобриков – Одесса, ОПИ, 1980. – 56 с.
Методические указания и задачи к практическим занятиям по курсу "Основы дискретной математики". /Сост. С.А. Нестеренко – Одесса, ОПИ, 1988, Ч.2. – 36 с.
Конспект лекцій до дисципліни «Основи дискретної математики» для студентів очної і заочної форм навчання фахів 6.0804 і 6.0915 факультету автоматики й обчислювальної техніки / Укл. О.М. Мартинюк. – Одеса: ОНПУ, 2001. – 124 с.
ЗМІСТ
Вступ 3
Теорія множин 4
Основи теорії множин 4
Упорядковані безлічі 7
Графіки 8
Відповідності, образи і прообрази 10
Відношення. Функції 13
Спеціальні види відносини 17
Замикання відношень 18
Спеціальні функції 19
Операції 20
Комбінаторика 21
Перестановки 21
Сполучення 22
Рекуррентные співвідношення 22
Біном Ньютона 23
Поліноміальні й експонентні виробляючі функції 23
Принцип включення і виключення 24
Розбивки 24
Булєва алгебра 24
Функції 24
Способи завдання булєвих функцій 25
Булєва алгебра 27
Булєва алгебра множин 30
Алгебра Жегалкіна 30
Типи булєвих функцій 31
Функціональна повнота 32
Логічні (перемикальні) схеми 33
Мінімізація булєвих функцій 35
Логіка предикатів 40
Графи 42
Основні визначення і способи представлення графів 42
Теоретико-множинні операції над графами 45
Чисельні характеристики графів 47
Кінцеві автомати 49
Абстрактний автомат. Робота абстрактного автомата. Способи завдання 49
Розширення функцій d і l 51
Синхронні й асинхронні автомати. Асинхронні тактуємі
автомати 52
Перетворення автоматів Мілі і Мура 52
Сполучена модель автоматів – С- автомат 54
Композиція автоматів 54
Список літератури 57
Зміст 58
Навчальне видання
Методичні вказівки і завдання до контрольних робіт за курсом «Основи дискретної математики» для студентів заочної форми навчання фахів 6.0804, 6.0915.
Укл.:
Олександр Миколайович Мартинюк
Редактор
З.І. Вальх, Т.І. Лучнкова
Коректор
Н.К. Филиппович
-----------------------------------------------------------------------------------------------
Підписано к друку 27.09.2001. Формат 60х84/16. Папір газетний.
Друк офсетний. ум.друк.арк. обл.-вид.арк.
Тираж 200 пр. Зам. №
-----------------------------------------------------------------------------------------------
Одеський національний політехнічний університет
65044, Одеса, пр. Шевченка, 1
