[ Абстрактний синтез кінцевого автомата ] | |
0011 | 1110 |
1110 | 1001 |
1.2 Приведення оператора до автоматної увазі
Для того щоб оператор перетворився до автоматної увазі, необхідне виконання трьох умов:
1. Будь-яким двом однаковим початковим відрізкам вхідних слів повинні відповідати однакові початкові відрізки вихідних слів;
2. Довжина вхідного слова повинна дорівнювати довжині вихідного слова;
3. Останній символ повинен повертати автомат в початковий стан.
Даний оператор уже вирівняний, так як довжина кожного з вхідних слів дорівнює довжині відповідного вихідного слова. Кожному вхідному слову тут зіставляються не більше одного вихідного слова, тому оператор однозначний. Однак він не задовольняє умову повноти.
Таким чином, автоматний вид оператора прийме, такий вигляд:
Таблиця 2. Автоматний вид
Вхідні сигнали | Вихідні сигнали |
0010 | 1111 |
0110 | 1110 |
1111 | 1000 |
1101 | 1000 |
00100000 | 11110011 |
1010 | 1011 |
0011 | 1110 |
1110 | 1001 |
1.3 Побудова графа переходів абстрактного автомата
Побудуємо за таблицею 2 граф переходів автомата. При цьому передбачається, що останній символ кожного вхідного слова повинен переводить автомат в початковий стан.
Граф переходів абстрактного автомата представлений у додатку 1.
1.4 Мінімізація абстрактного автомата
За графу переходів побудуємо таблицю переходів-виходів заданого автомата (таблиця 3).
Таблиця 3. Таблиця переходів-виходів автомата
a (t-1) | 0 | 1 |
a 0 | a 1 / 1 | a 2 / 1 |
a 1 | a 3 / 1 | a 4 / 1 |
a 2 | a 10 / 0 | a 11 / 0 |
a 3 | - | a 5 / 1 |
a 4 | - | a 6 / 1 |
a 5 | a 8 / 1 | a 9 / 0 |
a 6 | a 8 / 0 | - |
a 7 | a 0 / - | a 0 / - |
a 8 | a 0 / - | a 0 / - |
a 9 | a 0 / - | a 0 / - |
a 10 | - | a 12 / 1 |
a 11 | a 14 / 0 | a 15 / 0 |
a 12 | a 13 / 1 | - |
a 13 | a 0 / - | a 0 / - |
a 14 | - | a 16 / 0 |
a 15 | a 17 / 1 | a 18 / 0 |
a 16 | a 0 / - | a 0 / - |
a 17 | a 0 / - | a 0 / - |
a 18 | a 0 / - | a 0 / - |
Один з алгоритмів мінімізації повністю певних автоматів полягає в наступному. Безліч станів вихідного абстрактного автомата розбивається на попарно перетинаються класи еквівалентних станів, далі кожен клас еквівалентності замінюється одним станом. У результаті виходить мінімальний автомат, що має стільки ж станів, на скільки класів еквівалентності розбиваються вихідні стани автомата.
0 клас еквівалентності:
a 0, a 1 | b 0 |
a 2, a 11 | b 1 |
a 14 | b 2 |
a 3, a 4, a 10 | b 3 |
a 5, a 15 | b 4 |
a 6 | b 5 |
a 7, a 8, a 9, a 13, a 16, a 17, a 18 | b 6 |
a 12 | b 7 |
1 клас еквівалентності:
a 0 | c 0 |
a 1 | c 1 |
a 2 | c 2 |
a 3 | c 3 |
a 4 | c 4 |
a 5, a 15 | c 5 |
a 6 | c 6 |
a 10 | c 7 |
a 11 | c 8 |
a 12 | c 9 |
a 14 | c 10 |
a 7, a 8, a 9, a 13, a 16, a 17, a 18 | c 11 |
2 клас еквівалентності:
a 0 | d 0 |
a 1 | d 1 |
a 2 | d 2 |
a 3 | d 3 |
a 4 | d 4 |
a 5, a 15 | d 5 |
a 6 | d 6 |
a 10 | d 7 |
a 11 | d 8 |
a 12 | d 9 |
a 14 | d 10 |
a 7, a 8, a 9, a 13, a 16, a 17, a 18 | d 11 |
З розбиття видно, що класи 1 і 2 збігаються, значить, продовжувати не має сенсу.
Таблиця переходів-виходів мінімізованого автомата представлена в таблиці 4:
Таблиця 4. Таблиця переходів-виходів мінімізованого автомата
d (t-1)
Граф переходів мінімізованого автомата представлений в додатку 2. 2. СТРУКТУРНИЙ СИНТЕЗ КІНЦЕВОГО АВТОМАТА 2.1 Кодування станів, вхідних і вихідних сигналів Для кодування станів, вхідних і вихідних сигналів кінцевого автомата, необхідно обчислити кількість елементів пам'яті: а) розрахуємо кількість елементів пам'яті: Н =] log 2 h [, де h - число станів після мінімізації D = {} H =] log 2 грудня [= 4 б) розрахуємо кількість вхідних (L) і вихідних (М) шин: М =] log 2 m [, де n, m - кількість літер вхідного і вихідного алфавітів Z = {0, 1} L =] log 2 2 [= 1 W = {0, 1} M =] log 2 2 [= 1 З наведеного вище випливає, що для кодування станів необхідно 4 елемента пам'яті, позначимо їх Q 0, ..., Q 3. Закодуємо стану (таблиця 5) випадковими кодами. Таблиця 5. Таблиця кодованих станів
2.2 Формування функцій збудження і вихідних сигналів структурного автомата За мінімізованому графу переходів абстрактного автомата (Додаток 2) можна скласти таблицю переходів, вихідних сигналів і сигналів збудження D-тригерів автомата Мілі (таблиця 6), Т-тригерів автомата Мілі (таблиця 7), RS-тригерів (таблиця 8), JK - тригерів (таблиця 9). D-тригер - елемент затримки - має один інформаційний вхід D і один вихід Q і здійснює затримку надходження на його вхід сигналу на один такт. Стан, в яке переходить тригер, збігається з надійшли на його вхід сигналом D (t). Таблиця 6. Таблиця переходів, вихідних сигналів і сигналів збудження D-тригерів
| D 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 | d 0 | 0000 | d 1 d 2 | 0001 0010 | 0 1 | d 0 0 d 0 1 | d 0 1 | d 0 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2 | d 1 | 0001 | d 3 d 4 | 0011 0100 | 0 1 | d 1 0 d 1 січня | d 1 січня | d 1 0 | d 1 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3 | d 2 | 0010 | d 7 d 8 | 0111 1000 | 0 1 | d 2 0 d 1 лютого | d 1 лютого | d 2 0 | d 2 0 | d 2 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4 | d 3 | 0011 | d 5 | 0101 | 1 | d 3 січня | d 3 січня | d 3 січня | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5 | d 4 | 0100 | d 6 | 0110 | 1 | d 1 квітня | d 1 квітня | d 1 квітня | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
6 | d 5 | 0101 | d 11 | 1011 | 0 Ú 1 | d 5 0 | d 1 Травня | d 5 0 Ú d 1 Травня | QUOTE | d 5 0 Ú d 1 Травня | d 5 0 QUOTE Ú | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
7 | d 6 | 0110 | d 11 | 1011 | 0 | d 6 0 | d 6 0 | d 6 0 | d 6 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
8 | d 7 | 0111 | d 9 | 1001 | 1 | d 1 Липня | d 1 Липня | d 1 Липня | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
9 | d 8 | 1000 | d 10 d 5 | 1010 0101 | 0 1 | d 8 0 d 1 серпня | d 8 0 | d 1 серпня | d 8 0 | d 1 серпня | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
10 | d 9 | 1001 | d 11 | 1011 | 0 | d 9 0 | d 9 0 | d 9 0 | d 9 0
З таблиці випливає, що вихідні сигнали автомата Мілі описуються наступними виразами: = D 2 0 Ú d 1 лютого Ú d 5 0 Ú d 6 0 Ú d 8 0 Ú d 8 січня Ú d 10 Січня = d 2 Ú d 5 0 Ú d 6 0 Ú d 8 Ú d 10 січня = D 0 0 Ú d 0 1 Ú d 1 0 Ú d 1 січня Ú d 1 березня Ú d 4 січні Ú d 1 травня Ú d 1 липня Ú d 9 0 = D 0 Ú d 1 Ú d 1 березня Ú d 1 квітня Ú d 1 травня Ú d 1 липня Ú d 9 0 Також слід, що сигнали збудження D-тригерів автомата Мілі описуються наступними виразами: QUOTE D 3 = d 1 лютого Ú d 5 0 Ú d 1 травня Ú d 6 0 Ú d 1 липня Ú d 8 0 Ú d 9 0 Ú d 10 Січня = d 1 лютим Ú d 5 Ú d 6 0 Ú d 7 січня Ú d 8 0 Ú d 9 0 Ú d 10 січня D 2 = d 1 січня Ú d 2 0 Ú d 1 березня Ú d 4 січня Ú d 8 січня D 1 = d 0 1 Ú d 1 0 Ú d 2 0 Ú d 4 січня Ú d 5 0 Ú d 1 травня Ú d 6 0 Ú d 8 0 Ú d 9 0 Ú d 1 жовтня = = D 0 1 Ú d 1 0 Ú d 2 0 Ú d 1 квітня Ú d 5 Ú d 6 0 Ú d 8 0 Ú d 9 0 Ú d 10 Січня D 0 = d 0 0 Ú d 1 0 Ú d 2 0 Ú d 1 Березня Ú d 5 0 Ú d 1 травня Ú d 6 0 Ú d 1 липня Ú d 1 серпень Ú d 9 0 Ú d 1 жовтень = = D 0 0 Ú d 1 0 Ú d 2 0 Ú d 3 січня Ú d 5 Ú d 6 0 Ú d 1 липня Ú d 8 січня Ú d 9 0 Ú d 10 Січня Функціональна схема автомата Милі на D-тригерах, побудована за виразами, що описує вихідні сигнали, наведена у Додатку 3. Таблиця 7. Таблиця переходів, вихідних сигналів і сигналів збудження T-тригерів
d 0 1 | d 0 1 | d 0 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2 | d 1 | 0001 | d 3 d 4 | 0011 0100 | 0 1 | d 1 0 d 1 січня | d 1 січня | d 1 0 | d 1 січня | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3 | d 2 | 0010 | d 7 d 8 | 0111 1000 | 0 1 | d 2 0 d 1 лютого | d 1 лютого | d 2 0 | d 1 лютого | d 2 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4 | d 3 | 0011 | d 5 | 0101 | 1 | d 3 січня | d 3 січня | d 3 січня | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5 | d 4 | 0100 | d 6 | 0110 | 1 | d 1 квітня | d 1 квітня | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
6 | d 5 | 0101 | d 11 | 1011 | 0 Ú 1 | d 5 0 | d 1 Травня | d 5 0 Ú d 1 Травня | d 5 0 Ú d 1 Травня | d 5 0 Ú d 1 Травня | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
7 | d 6 | 0110 | d 11 | 1011 | 0 | d 6 0 | d 6 0 | d 6 0 | d 6 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
8 | d 7 | 0111 | d 9 | 1001 | 1 | d 1 Липня | d 1 Липня | d 1 Липня | d 1 Липня | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
9 | d 8 | 1000 | d 10 d 5 | 1010 0101 | 0 1 | d 8 0 d 1 серпня | d 1 серпня | d 1 серпня | d 8 0 | d 1 серпня | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
10 | d 9 | 1001 | d 11 | 1011 | 0 | d 9 0 | d 9 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
11 | d 10 | 1010 | d 11 | 1011 | 1 | d 1 жовтень | d 1 жовтень | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
12 | d 11 | 1011 | d 0 | 0000 | - | - | - | - | - | - | - |
З таблиці випливає, що сигнали збудження T-тригерів автомата Мілі описуються наступними виразами:
T 3 = d 1 лютого Ú d 5 0 Ú d 1 травня Ú d 6 0 Ú d 1 липень Ú d 1 Серпень = d 2 січня Ú d 5 Ú d 6 0 Ú d 7 січня Ú d 1 серпня
T 2 = d 1 січня Ú d 2 0 Ú d 1 березня Ú d 5 0 Ú d 5 січня Ú d 6 0 Ú d 1 липні Ú d 8 січня = d 1 січня Ú d 2 0 Ú d 3 січня Ú d 5 Ú d 6 0 Ú d 7 січня Ú d 1 серпня
T 1 = d 0 1 Ú d 1 0 Ú d 1 лютого Ú d 1 Березня Ú d 4 січні Ú d 5 0 Ú d 5 січня Ú d 1 липня Ú d 8 0 Ú d 9 0 = d 0 1 Ú d 1 0 Ú d 1 лютого Ú d 1 березня Ú d 1 квітня Ú d 5 Ú d 1 липні Ú d 8 0 Ú d 9 0
T 0 = d 0 0 Ú d 2 0 Ú d 6 0 Ú d 1 серпня Ú d 1 жовтня
Функціональна схема автомата Милі на T-тригерах, побудована за виразами, що описує вихідні сигнали, наведено у Додатку 4.
Таблиця 8. Таблиця переходів і сигналів збудження RS-тригерів
Номер переходу | Сигнали порушення | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
R 3 | S 3 | R 2 | S 2 | R 1 | S 1 | R 0 | S 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 | d 0 1 | d 0 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2 | d 1 січня | d 1 0 | d 1 січня | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3 | d 1 лютого | d 2 0 | d 1 лютого | d 2 0 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4 |
З таблиці випливає, що сигнали збудження RS-тригерів автомата Мілі описуються наступними виразами: R 3 = d 8 січня S 3 = d 2 січня Ú d 5 0 Ú d 1 Травень Ú d 6 0 Ú d 1 Липня Ú d 9 0 = d 2 січня Ú d 5 Ú d 6 0 Ú d 7 січня Ú d 9 0 R 2 = d 5 0 Ú d 1 Травня Ú d 6 0 Ú d 1 Липня = d 5 Ú d 6 0 Ú d 1 липня S 2 = d 1 січня Ú d 2 0 Ú d 1 Березня Ú d 1 серпня R 1 = D 2 січня Ú d 1 березня Ú d 1 липня S 1 = d 0 1 Ú d 1 0 Ú d 1 квітня Ú d 5 0 Ú d 1 травня Ú d 8 0 = d 0 1 Ú d 1 0 Ú d 4 січня Ú d 5 Ú d 8 0 R 0 = D 1 січня S 0 = d 0 0 Ú d 2 0 Ú d 6 0 Ú d 8 січня Ú d 1 жовтень QUOTE QUOTE Функціональна схема автомата Милі на RS-тригерах, побудована за виразами, що описує вихідні сигнали, наведена в Додатку 5. Таблиця 9. Таблиця переходів і сигналів збудження JK-тригерів
З таблиці випливає, що сигнали збудження RS-тригерів автомата Мілі описуються наступними виразами: J 3 = d 2 січня Ú d 5 0 Ú d 1 Травень Ú d 6 0 Ú d 1 Липня Ú d 9 0 = d 2 січня Ú d 5 Ú d 6 0 Ú d 1 липня Ú d 9 0 K 3 = d 8 січня J 2 = d 1 січня Ú d 2 0 Ú d 1 Березня Ú d 1 серпня K 2 = d 5 0 Ú d 1 травень Ú d 6 0 Ú d 1 липень = d 5 Ú d 6 0 Ú d 1 липня J 1 = d 0 1 Ú d 1 0 Ú d 1 квітня Ú d 5 0 Ú d 1 травня Ú d 8 0 = d 0 1 Ú d 1 0 Ú d 4 січня Ú d 5 Ú d 8 0 K 1 = d 2 січень d 1 березня d 1 липня J 0 = d 0 0 Ú d 2 0 Ú d 6 0 Ú d 1 серпня Ú d 1 жовтня K 0 = d 1 січня Функціональна схема автомата Милі на JK-тригерах, побудована за виразами, що описує вихідні сигнали, наведена в Додатку 6. ВИСНОВОК У процесі виконання роботи мною були закріплені знання про синтез кінцевих автоматів і отримана практика в побудові комбінаційних схем. У даній роботі мною було виконано проектування кінцевого автомата за алфавітним відображенню з використанням канонічного методу структурного синтезу автоматів. Побудовано граф переходів абстрактного автомата з 17 станами і таблиці переходів-виходів. Мінімізація станів автомата виконана шляхом розбиття на групи еквівалентних між собою станів. Після чого був побудований мінімальний граф Мілі з 11 станами. Виконано структурний синтез кінцевого автомата. Побудовано функціональні схеми автомата Милі на D, T, RS і JK-тригерах. СПИСОК ЛІТЕРАТУРИ
|