Лекции.Орг


Поиск:




Синхронні й асинхронні автомати. Асинхронні тактуємі автомати




Задачі

Визначити, чи є асинхронним автомат Мура, заданий на рис. 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

 





Поделиться с друзьями:


Дата добавления: 2015-11-05; Мы поможем в написании ваших работ!; просмотров: 540 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Люди избавились бы от половины своих неприятностей, если бы договорились о значении слов. © Рене Декарт
==> читать все изречения...

1017 - | 836 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.