Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Міністерство освіти і науки України
Тернопільський національний технічний університет імені Івана Пулюя
Кафедра компютерних систем та мереж
Практична робота №1
Мінімізація автомата Мілі.
Виконав:
студент гр. СІ-21
Крутиголова О. І.
Прийняла:
Шингера Н. Я.
Тернопіль 2013
Тема: Мінімізація автомата Мілі.
Мета: Навчитися мінімізувати автомат Мілі
Таблиця переходів
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
a9 |
a10 |
a11 |
a12 |
|
z1 |
a4 |
a12 |
a5 |
a7 |
a5 |
a7 |
a2 |
a4 |
a7 |
a1 |
a5 |
a2 |
z2 |
a5 |
а7 |
а7 |
a11 |
a6 |
a10 |
a6 |
a10 |
a5 |
a7 |
a9 |
a8 |
Таблиця виходів
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
a9 |
a10 |
a11 |
a12 |
|
z1 |
w1 |
w1 |
w2 |
w2 |
w1 |
w2 |
w1 |
w1 |
w2 |
w2 |
w2 |
w2 |
z2 |
w2 |
w2 |
w1 |
w1 |
w2 |
w1 |
w2 |
w2 |
w1 |
w1 |
w1 |
w1 |
Розбиваємо внутрішні стани на групи відповідно до кількості комбінацій вихідних сигналів. У нашому випадку буде дві групи В1 і В2.
B1 = {a1, a2, a5, a7, a8}
B2 = {a3, a4, a6, a9, a10, a11, a12}
Таблиця розбиття
a1 |
a2 |
а5 |
а7 |
а8 |
а3 |
а4 |
а6 |
a9 |
a10 |
a11 |
a12 |
||
z1 |
B2 |
B2 |
B1 |
B1 |
B1 |
B1 |
B2 |
B1 |
B1 |
B1 |
B1 |
B1 |
|
z2 |
B1 |
B1 |
B2 |
B2 |
B2 |
B1 |
B2 |
B1 |
B1 |
B1 |
B2 |
B1 |
Окремо розбиваємо на класи блоки В1 і В2
C1 = { a1, a2 }
C2 = { a5; a7; a8; }
C3 = { a3; a9; a10; a12, }
С4 = { а4; а6; а11 }
a1 |
a2 |
а5 |
а7 |
а8 |
а3 |
a9 |
a10 |
a12 |
a4 |
а6 |
a11 |
|
z1 |
C5 |
C4 |
C2 |
C1 |
C5 |
C2 |
C3 |
C2 |
C1 |
C3 |
C3 |
C1 |
z2 |
C2 |
C3 |
C4 |
C4 |
C4 |
C3 |
C2 |
C4 |
C3 |
C3 |
C4 |
C3 |
Окремо розбиваємо на класи блоки С1 і С2
D1 = {a1}
D2 = {a2}
D3 = {a5}
D4 = {a7}
D5 = {a8}
D6 = {a11}
D7 = {a3}
D8 = {a6}
D9 = { а9}
D10 = { a10,a12}
D11 = {a4}
a1 |
a2 |
а5 |
а7 |
а8 |
a11 |
а3 |
а6 |
a9 |
a10 |
a12 |
a4 |
|
z1 |
D11 |
D10 |
D3 |
D2 |
D11 |
D3 |
D3 |
D4 |
D4 |
D1 |
D10 |
D4 |
z2 |
D3 |
D4 |
D8 |
D8 |
D10 |
D9 |
D4 |
D10 |
D3 |
D4 |
D5 |
D6 |
Окремо розбиваємо на класи блоки E1 і E2
E1 = {a1}
E2 = {а2}
E3 = {a5}
E4 = {a7 }
E5 = {a8}
E6 = {a11}
E7 = {a3}
E8 = {a6}
Е9 = {a9}
Е10 = {a10}
E11 = {a12}
E12 = {a4}
a1 |
a2 |
а5 |
а7 |
а8 |
a11 |
а3 |
а6 |
a9 |
a10 |
a12 |
a4 |
|
z1 |
E12 |
E11 |
E3 |
E2 |
E12 |
E3 |
E3 |
E4 |
E4 |
E1 |
E2 |
E4 |
z2 |
E3 |
E4 |
E8 |
E8 |
E10 |
E9 |
E4 |
E10 |
E3 |
E4 |
E5 |
E6 |
Окремо розбиваємо на класи блоки F1 і F2
F1 = {a1}
F2 = {а2}
F3 = {a5}
E4 = {a7 }
F5 = {a8}
F6 = {a11}
F7 = {a3}
F8 = {a6}
F9 = {a9}
F10 = {a10}
F11 = {a12}
F12 = {a4}
Порівнявши класи E і F бачимо, що вони співпадають, робимо висновок, що мінімізований автомат буде містити 12 станів.
Вибираємо з кожного класу Fі по одному стану і отримуємо множину станів А мінімального автомату.
А = {а1, а2, а3, a4 а5, а6, a7, a8, a9, a10, а11, a12}
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
a9 |
a10 |
a11 |
a12 |
|
z1 |
a4 |
a12 |
a5 |
a7 |
a5 |
a7 |
a2 |
a4 |
a7 |
a1 |
a5 |
a2 |
z2 |
a5 |
а7 |
а7 |
a11 |
a6 |
a10 |
a6 |
a10 |
a5 |
a7 |
a9 |
a8 |
Висновок: на цій практичній роботі ми навчилися мінімізувати цифровий автомат Мілі, розбиваючи внутрішні стани на групи відповідно до кількості комбінацій вихідних сигналів і окремо розбиваючи на класи блоки.