Міністерство науки і освіти України Національний університет “Львівська політехніка” Інститут прикладної математики і фундаментальних наук Кафедра прикладної математики Розрахункова робота з теорії систем на тему: “Синтез автоматних моделей” Постановка задачі. Варіант № 23. Синтезувати автоматну модель системи із заданим відображенням і набором елементів пам'яті Відображення системи:

, де ] t [ — найменше ціле не менше t,

.
Рис. 1. Відображення системи Елементи пам'яті: Елемент 4 Y 0 1   U X 0 1  1 0 1  0 1 0   Розміщення елементів пам'яті: 4, 23, 23, … Зведення відображення системи до автоматного. Виконаємо квантування і дискретизацію відображення системи. Нехай нам задано множину моментів часу системи Ts
. Після дискретизації Ts отримаємо множину
:
Нехай Ys – множина вихідних формальних параметрів системи
, тоді в результаті квантування Ys отримаємо множину
:
Графік квантованого і дискретизованого відображення системи наведений на рис. 2
Рис. 2. Графік дискретизованого і квантованого відображення системи Введемо додаткове відображення
, причому
. Нехай
, тоді
Побудуємо алфавітний оператор. Для цього використаємо рис.2 і додаткове відображення f. Отже, отримаємо алфавітний оператор А: x→ y0  xx→ y1  xxx→ y2  xxxx→ y3  xxxxx→ y0   Отриманий алфавітний оператор А є повним і однозначним тому зведення його до автоматного не є обов’язковим. Тепер побудуємо канонічну множину подій. Нехай
множина подій у вхідному алфавіті, що зображається літерою
. Тоді SY0 ={x,xxxxx,xxxxxxxxx,…} SY1 ={xx,xxxxx,…} SY2 ={xxx,xxxxxx,…} SY3 ={xxxx,xxxxxxx,…} На основі отриманих канонічних множин подій побудуємо регулярний вираз кожної події. Отримаємо: y0 = xxxxxxxxxxxxxxx.......=x(εxxxxxxxxxxxx)=x<xxxx> y1 = xxxxxxxx………..=xx<xxxxx> y2 = xxxxxxxxxx…….=xxx<xxxxx> y3 = xxxxxxxxxxx……=xxx<xxxx> Синтез абстрактного автомата. Для синтезу абстрактного автомата використовуємо метод Глушкова. Зведемо отримані регулярні вирази до правильних і виконаємо розмітку, застосовуючи правила підпорядкування місць. y0 =
x
<
x
x
x
x
>
y1 =
x
x
<
x
x
x
x
>
y2 =
x
x
x
<
x
x
x
x
>
y3 =
x
x
x
x
<
x
x
x
x
>
Використовуючи отриману розмітку побудуємо таблицю автомата. Y - y0 y1 y2 y3 y0  X\Y 0 1,6,12,19 2,7,13,20 3,8,14,21 4,9,15,22 5,10,16,23  x 1,6,12,19 2,7,13,20 3,8,14,21 4,9,15,22 5,10,16,23 2,11,17,24   Y y1 y2 y3 y0  X\Y 2,11,17,24 3,8,18,25 4,9,15,26 5,10,16,23  x 3,8,18,25 4,9,15,26 5,10,16,23 2,11,17,24  Таблиця 1. Таблиця автомата Мінімізуємо дану таблицю і перепозначимо стани автомата. Y - y0 y1 y2 y3  X\Y 0 1 2 3 4  x 1 2 3 4 1  Таблиця 2. Мінімізована таблиця автомата з перепозначеними станами. Використовуючи таблицю 2 побудуємо граф автомата. Граф автомата зображено на рис. 3. x x Рис. 3. Граф автомата Синтез структурного автомата. Будуємо фізичну таблицю переходів. Кількість елементів пам'яті і кількість розрядів для кодування входів, станів і наборів подій автомата визначаємо з формул
, і
. Проведемо кодування входів, виходів та станів: 0=000 x=0 1=001 y0=00 2=010 y1=01 3=011 y2=10 4=100 y3=11 Тепер побудуємо таблицю переходів: Y - 00 01 10 11  X\Y 000 001 010 011 100  0 001 010 011 100 001   Таблиця 3. Фізична таблиця переходів. Будуємо таблицю збуджень. Елементами таблиці збуджень є ті сигнали, які треба подати на елементи пам'яті, щоб здійснити вказані в фізичній таблиці переходи. В результаті отримаємо: Y - 00 01 10 11  X\Y 000 001 010 011 100  0 10--1 1-10- 1-1-1 00-0- 00--1  Таблиця 4. Таблиця збуджень Синтез комбінаційної схеми. Нехай:
– функції входів елемента пам'яті ЕП1,
– функції входів елемента пам'яті ЕП2,
– функції входів елемента пам'яті ЕП3, z1, z2, z3 – стани елементів пам’яті ЕП1, ЕП2, ЕП3,
– функції виходів автомата. Використовуючи метод карт К...