Дискретный анализ и теория автоматов. Методические указания для самостоятельной работы студента
.pdf
|
|
7 |
|
(v5, v4) |
|
11 |
4 |
13, 27, 8, 15 |
6 |
(v1, v2), (v1, v3), (v2, v3), (v2, v4), (v3, v3), (v4, v1) |
13, 27, 8, 15, 20, 10 |
12 |
4 |
7, 12, 23, 16 |
6 |
(v1, v3), (v1, v5), (v2, v2), (v2, v3), (v3, v4), (v4, v2) |
7, 12, 23, 16, 15, 20 |
13 |
4 |
5, 7, 9, 10 |
6 |
(v1, v2), (v1, v2), (v1, v3), (v2, v1), (v2, v4), (v4, v4) |
5, 7, 9, 10, 14, 18 |
14 |
4 |
5, 20, 12, 15 |
6 |
(v1, v4), (v1, v4), (v2, v3), (v2, v4), (v3, v3), (v4, v1) |
5, 20, 12, 15, 17, 8 |
15 |
4 |
9, 24, 16, 24 |
6 |
(v1, v2), (v1, v4), (v2, v2), (v2, v3), (v3, v4), (v3, v1) |
9, 24, 16, 24, 32, 51 |
16 |
4 |
7, 21, 15, 10 |
6 |
(v1, v2), (v1, v3), (v2, v2), (v2, v4), (v3, v4), (v4, v2) |
7, 21, 15, 10, 20, 31 |
17 |
4 |
5, 7, 15, 10, |
6 |
(v1, v2), (v1, v2), (v1, v3), (v2, v4), (v4, v3), (v3, v1) |
5, 7, 15, 10, 14, 16 |
18 |
4 |
8, 9, 6, 11 |
6 |
(v1, v1), (v1, v4), (v2, v4), (v2, v1), (v3, v4), (v4, v1) |
8, 9, 6, 11, 7, 9 |
19 |
4 |
6, 8, 15, 10 |
6 |
(v1, v2), (v1, v3), (v2, v3), (v2, v4), (v4, v3), (v4, v3) |
6, 8, 15, 10, 9, 10 |
20 |
4 |
9, 11, 16, 7 |
6 |
(v1, v3), (v1, v4), (v2, v3), (v3, v4), (v4, v4), (v4, v2) |
9, 11, 16, 7, 11, 16 |
21 |
5 |
13, 25, 8, |
7 |
(v1, v1), (v1, v3), (v2, v3), (v2, v4), (v4, v1), (v4, v5), |
13, 25, 8, 37, 14, 24, |
|
|
37, 14 |
|
(v5, v2) |
16 |
|
|
Продовження табл. 20 |
|
||
№ |
n |
h1, …, hn |
m |
e1, ..., em |
p1, …, pm |
22 |
5 |
8, 12, 54, |
7 |
(v1, v3), (v1, v5), (v2, v2), (v2, v3), (v3, v4), (v3, v5), |
8, 12, 54, 26, 16, 21, |
|
|
26, 16 |
|
(v5, v1) |
15 |
23 |
5 |
7, 12, 15, 9, |
7 |
(v1, v3), (v1, v3), (v2, v2), (v2, v5), (v3, v4), (v4, v5), |
7, 12, 15, 9, 10, 9, 11 |
|
|
10 |
|
(v5, v3) |
|
24 |
5 |
8, 8, 20, 16, |
7 |
(v1, v2), (v1, v4), (v1, v4), (v2, v3), (v2, v5), (v4, v5), |
8, 8, 20, 16, 15, 11, |
|
|
15 |
|
(v5, v1) |
16 |
25 |
5 |
9, 14, 24, |
7 |
(v1, v2), (v1, v3), (v1, v4), (v1, v5), (v2, v3), (v2, v4), |
9, 14, 24, 16, 20, 21, |
|
|
16, 20 |
|
(v4, v5) |
15 |
26 |
5 |
9, 21, 10, |
7 |
(v1, v2), (v1, v5), (v2, v3), (v2, v4), (v3, v4), (v3, v5), |
9, 21, 10, 15, 12, 7, |
|
|
15, 12 |
|
(v4, v5) |
15 |
27 |
5 |
9, 7, 19, 10, |
7 |
(v1, v2), (v1, v2), (v1, v3),(v2, v4), (v2, v5), (v4, v5), |
9, 7, 19, 10, 8, 8, 15 |
|
|
8 |
|
(v5, v1) |
|
28 |
5 |
10, 9, 10, |
7 |
(v1, v1), (v1, v2), (v1, v4), (v2, v3), (v2, v4), (v2, v5), |
10, 9, 10, 16, 11, 14, |
|
|
16, 11 |
|
(v3, v5) |
16 |
29 |
4 |
6, 8, 21, 17 |
6 |
(v1, v2), (v1, v4), (v2, v3), (v2, v4), (v3, v4), (v4, v1) |
6, 8, 21, 17, 15, 10 |
|
|
|
|
|
|
30 |
4 |
8, 9, 16, 7 |
6 |
(v1, v2), (v1, v4), (v2, v3), (v2, v4), (v3, v1), (v4, v2) |
8, 9, 16, 7, 11, 7 |
31 |
4 |
10, 27, 10, |
6 |
(v1, v2), (v1, v3), (v2, v3), (v3, v3), (v3, v4), (v4, v1) |
10, 27, 10, 15, 15, 10 |
|
|
15 |
|
|
|
32 |
4 |
7, 15, 23, 18 |
6 |
(v1, v3), (v1, v4), (v2, v3), (v3, v1), (v3, v4), (v4, v4) |
7, 15, 23, 18, 8, 15 |
|
|
|
|
|
|
33 |
4 |
10, 7, 9, 15 |
6 |
(v1, v2), (v1, v3) ,(v1, v3), (v2, v3), (v3, v4), (v4, v2) |
10, 7, 9, 15, 16, 7 |
34 |
4 |
5, 20, 10, 10 |
6 |
(v1, v1), (v1, v2), (v1, v4), (v2, v3), (v3, v4), (v4, v1) |
5, 20, 10, 10, 11, 16 |
35 |
4 |
9, 20, 10, 25 |
6 |
(v1, v3), (v1, v4), (v2, v1), (v3, v4), (v4, v1), (v4, v4) |
9, 20, 10, 25, 20, 16 |
Завдання 3
Неорієнтований зважений граф подано його діаграмою на рис. 20. Ваги ребер (в умовних одиницях) наведені у табл.21, де позначки ∞ та 1 означають відповідно відсутність та наявність ребра (варіативно).
61
v1 |
v4 |
v7 |
v3 |
|
v6 |
v0 |
|
v9 |
v2 |
v5 |
v8 |
Рисунок 20 – Неорієнтований зважений граф
62
Таблиця 21 – Варіативне задання зваженого графу
№ |
|
|
|
|
|
Індекси вершин, інцидентних ребру |
|
|
|
|
|
||||||||
вар. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0;1 |
0;2 |
0;3 |
1;3 |
1;4 |
2;3 |
2;5 |
3;4 |
3;5 |
3;6 |
4;6 |
4;7 |
5;6 |
5;8 |
6;7 |
6;8 |
6;9 |
7;9 |
8;9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вага ребра |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
9 |
12 |
6 |
4 |
6 |
7 |
10 |
7 |
11 |
2 |
6 |
4 |
9 |
8 |
5 |
4 |
3 |
9 |
1, 11, |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
|
1 |
1 |
21, 31 |
|||||||||||||||||||
2, 12, |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
22, 32 |
|||||||||||||||||||
3, 13, |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
23, 33 |
|||||||||||||||||||
4, 14, |
1 |
1 |
1 |
|
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
24, 34 |
|||||||||||||||||||
5, 15, |
1 |
1 |
1 |
|
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
25, 35 |
|||||||||||||||||||
6, 16, |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
26, 36 |
|||||||||||||||||||
7, 17, |
1 |
1 |
|
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
27, 37 |
|||||||||||||||||||
8, 18, |
1 |
1 |
|
1 |
1 |
1 |
1 |
|
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
28, 38 |
|||||||||||||||||||
9, 19, |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
29, 39 |
|||||||||||||||||||
10, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20, |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
30, 40 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Потрібно побудувати неорієнтований граф на підставі базового графа, поданого на рис. 20, з варіативним виключенням ребер згідно табл. 21 та виконати наступне:
1)побудувати найкоротший кістяк (кістяковий підграф, кістякове дерево) цього графу, взявши за початкову вершину v0 для варіантів 1–10, v3 для варіантів 11–20, v6 для варіантів 21–30, v4 для варіантів 31–40. Така задача розв’язується, наприклад, у проектах кабельних мереж Internet;
2)неорієнтований граф, одержаний у п.1), перетворити в мережу. Ваги ребер вважати їхньою пропускною здатністю. За витік та стік взяти такі вершини: для варіантів 1–10 витік – х0, стік – х9; для варіантів 11–20 витік – х1, стік – х9; для варіантів 21–30 витік – х2, стік – х9; для варіантів 31–40 витік – х2, стік – х7. Орієнтацію ребер, неінцидентних витоку і стоку, вибрати за власним розсудом, щоб одержати саме мережу;
3)визначити пропускну здатність мережі, що одержана у п.2).
4.4 Розділ 4. Скінченні автомати. Постановка завдань
Завдання 1
На підставі базової поміченої таблиці переходів автомата Мура (табл. 22) побудувати варіативно задану таблицю переходів методом видалення стовпців згідно варіанта (табл. 23).
63
Таблиця 22 – Базова таблиця переходів автомата Мура
z(t) |
z1 |
z2 |
z3 |
z4 |
z5 |
z6 |
z7 |
z8 |
z9 |
z10 |
z11 |
z12 |
|
||||||||||||
w(t), q(t) |
|
|
|
|
|
|
|
|
|
|
|
|
|
w0, q0 |
q1 |
q3 |
q2 |
q |
4 |
q |
4 |
q0 |
q2 |
q1 |
q |
2 |
q |
4 |
q |
2 |
q2 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
w1, q1 |
q |
2 |
q |
4 |
q1 |
q0 |
q |
4 |
q3 |
q0 |
q3 |
q3 |
q2 |
q |
4 |
q0 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
w2, q2 |
q0 |
q0 |
q2 |
q3 |
q2 |
q1 |
q0 |
q2 |
q0 |
q2 |
q1 |
q3 |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
w3, q3 |
q3 |
q0 |
q3 |
q2 |
q1 |
q |
4 |
q |
4 |
q2 |
q1 |
q3 |
q |
4 |
q0 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
w4, q4 |
q |
4 |
q0 |
q |
4 |
q0 |
q2 |
q3 |
q0 |
q3 |
q2 |
q1 |
q2 |
q |
4 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
Таблиця 23 – Варіативне задання видалень |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
№ |
|
Змінні zi вхідного алфавіту, що |
|
|
|
№ |
|
|
|
Змінні zi вхідного алфавіту, що |
||||||||||||||||
|
вар. |
|
|
|
видаляються |
|
|
|
|
|
|
вар. |
|
|
|
|
видаляються |
|
|
|
|
||||||
|
1 |
|
z3, z4, z7, z8, z9, z10, z11, z12 |
|
|
|
|
|
|
19 |
|
|
z1, z4, z6, z7, z8, z10, z11, z12 |
|
|
|
|
||||||||||
|
2 |
|
z2, z3, z5, z6, z9, z10, z11, z12 |
|
|
|
|
|
|
20 |
|
|
z1, z2, z7, z8, z9, z10, z11, z12 |
|
|
|
|
||||||||||
|
3 |
|
z2, z4, z5, z6, z9, z10, z11, z12 |
|
|
|
|
|
|
21 |
|
|
z1, z2, z4, z5, z7, z8, z11, z12 |
|
|
|
|
||||||||||
|
4 |
|
z2, z3, z6, z7, z9, z10, z11, z12 |
|
|
|
|
|
|
22 |
|
|
z1, z2, z5, z6, z7, z8, z10, z11 |
|
|
|
|
||||||||||
|
5 |
|
z1, z4, z5, z6, z7, z10, z11, z12 |
|
|
|
|
|
|
23 |
|
|
z1, z4, z3, z5, z7, z9, z10, z12 |
|
|
|
|
||||||||||
|
6 |
|
z1, z2, z5, z6, z9, z10, z11, z12 |
|
|
|
|
|
|
24 |
|
|
z2, z3, z4, z6, z7, z8, z9, z10 |
|
|
|
|
||||||||||
|
7 |
|
z1, z2, z4, z5, z8, z10, z11, z12 |
|
|
|
|
|
|
25 |
|
|
z2, z3, z5, z6, z7, z8, z9, z12 |
|
|
|
|
||||||||||
|
8 |
|
z1, z2, z7, z8, z9, z10, z11, z12 |
|
|
|
|
|
|
26 |
|
|
z1, z3, z4, z6, z7, z8, z9, z10 |
|
|
|
|
||||||||||
|
9 |
|
z1, z3, z5, z6, z7, z10, z11, z12 |
|
|
|
|
|
|
27 |
|
|
z1, z3, z4, z5, z7, z8, z9, z12 |
|
|
|
|
||||||||||
|
10 |
|
z1, z3, z6, z7, z8, z10, z11, z12 |
|
|
|
|
|
|
28 |
|
|
z2, z4, z5, z6, z8, z9, z10, z12 |
|
|
|
|
||||||||||
|
11 |
|
z1, z2, z6, z7, z8, z10, z11, z12 |
|
|
|
|
|
|
29 |
|
|
z2, z3, z4, z6, z7, z8, z11, z12 |
|
|
|
|
||||||||||
|
12 |
|
z1, z2, z4, z5, z8, z9, z10, z12 |
|
|
|
|
|
|
30 |
|
|
z2, z3, z4, z7, z8, z9, z10, z11 |
|
|
|
|
||||||||||
|
13 |
|
z2, z3, z4, z5, z8, z9, z10, z11 |
|
|
|
|
|
|
31 |
|
|
z1, z2, z3, z6, z7, z8, z9, z11 |
|
|
|
|
||||||||||
|
14 |
|
z2, z3, z4, z7, z8, z9, z10, z12 |
|
|
|
|
|
|
32 |
|
|
z1, z2, z3, z5, z7, z8, z9, z11 |
|
|
|
|
||||||||||
|
15 |
|
z1, z2, z3, z8, z9, z10, z11, z12 |
|
|
|
|
|
|
33 |
|
|
z1, z2, z3, z4, z7, z8, z9, z10 |
|
|
|
|
||||||||||
|
16 |
|
z5, z6, z7, z8, z9, z10, z11, z12 |
|
|
|
|
|
|
34 |
|
|
z4, z5, z6, z8, z9, z10, z11, z12 |
|
|
|
|
||||||||||
|
17 |
|
z2, z3, z5, z6, z8, z9, z11, z12 |
|
|
|
|
|
|
35 |
|
|
z1, z2, z3, z4, z5, z10, z11, z12 |
|
|
|
|
||||||||||
|
18 |
|
z1, z6, z7, z8, z9, z10, z11, z12 |
|
|
|
|
|
|
36 |
|
|
z2, z3, z4, z5, z7, z8, z9, z10 |
|
|
|
|
||||||||||
У верхньому рядку таблиці 23 зазначені змінні zi алфавіту входу, які потрібно видалити, після цього звести індексацію залишених змінних zi до вигляду послідовності чисел натурального ряду від 1 до 4. Внаслідок буде одержано задану таблицю переходів автомата, після цього потрібно виконати наступне:
1)побудувати орграф заданого автомата Мура;
2)побудувати граф-схему алгоритма роботи заданого автомата Мура, взявши стан
q0 за початковий.
Нагадаємо основні властивості абстрактного автомата Мура. Насамперед помітимо, що в будь-якому автоматі (Мура або Мілі) перехід від поточного такту автоматного часу до наступного такту і зміна його стану відбуваються одночасно. В автоматі Мура в цей самий момент часу відбувається і зміна вихідного сигналу (елемента алфавіту виходу), причому із
64
кожним станом автомата (елементом алфавіту станів) пов’язана певна змінна виходу. Це |
||||||||||||
означає, що діяльність автомата Мура зводиться, по суті, до зміни його станів під час |
||||||||||||
переходу від поточного такту до наступного. Іншими словами, в автоматі Мура початок |
||||||||||||
кожного такту t автоматного часу (t – номер такту) зазначається поточним станом і сигналом |
||||||||||||
на виході автомата |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
q(t)= (q(t −1), z(t −1)), w(t) = (q(t)), |
|
|
|
||||||
після цього ідентифікується вхідна змінна і визначається стан автомата на наступному такті: |
||||||||||||
|
|
|
|
|
q(t +1)= (q(t), z(t)). |
|
|
|
|
|
||
Наслідком такого алгоритму діяльності є те, що реакція автомата на ідентифіковану вхідну |
||||||||||||
змінну z(t) виявляється із запізненням на один такт у вигляді сигналу на виході |
|
|
||||||||||
|
|
|
|
|
w(t +1) = (q(t +1)) . |
|
|
|
|
|
||
|
|
|
|
|
|
Завдання 2 |
|
|
|
|
|
|
|
На підставі базової таблиці переходів-виходів автомата Мілі (табл. 24) побудувати |
|||||||||||
варіативно задану таблицю переходів-виходів методом видалення стовпців згідно варіанта |
||||||||||||
(табл. 25). |
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблиця 24 – Базова таблиця переходів-виходів автомата Мілі |
|
|
|
||||||||
z(t) |
|
|
|
|
|
|
|
|
|
|
|
|
q(t) |
z1 |
z2 |
z3 |
z4 |
z5 |
z6 |
z7 |
z8 |
z9 |
z10 |
z11 |
z12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
q1 |
q3 |
q2 |
q0 |
q2 |
q0 |
q2 |
q1 |
q2 |
q1 |
q2 |
q2 |
q0 |
w3 |
w |
w1 |
w |
w4 |
w |
w3 |
w2 |
w |
w2 |
w |
w3 |
|
||||||||||||
|
|
4 |
|
4 |
|
1 |
|
|
2 |
|
2 |
|
|
q2 |
q2 |
q1 |
q0 |
q3 |
q3 |
q0 |
q3 |
q3 |
q2 |
q0 |
q0 |
q1 |
w |
w3 |
w2 |
w |
w |
w |
w |
w |
w |
w4 |
w |
w |
|
||||||||||||
|
2 |
|
|
2 |
3 |
1 |
2 |
3 |
1 |
|
1 |
4 |
|
q0 |
q0 |
q2 |
q3 |
q2 |
q1 |
q0 |
q2 |
q0 |
q2 |
q1 |
q3 |
q2 |
w1 |
w4 |
w4 |
w4 |
w1 |
w3 |
w4 |
w4 |
w1 |
w1 |
w3 |
w4 |
|
||||||||||||
|
q3 |
q0 |
q3 |
q2 |
q1 |
q2 |
q3 |
q2 |
q1 |
q3 |
q3 |
q0 |
q3 |
w1 |
w2 |
w3 |
w3 |
w2 |
w2 |
w4 |
w1 |
w3 |
w3 |
w1 |
w2 |
|
||||||||||||
|
У верхньому рядку таблиці 25 вказані змінні zi вхідного алфавіту, які потрібно |
|||||||||||
видалити, після цього звести індексацію залишених змінних zi до вигляду послідовності |
||||||||||||
чисел натурального ряду від 1 до 4. Внаслідок буде одержано задану таблицю переходів- |
||||||||||||
виходів автомата, після цього потрібно виконати наступне: |
|
|
|
|
||||||||
1)побудувати орграф заданого автомата Мілі;
2)побудувати граф-схему алгоритму роботи заданого автомата Мілі за умови, що у
початковому стані q0 , коли на вхід не подається жодна змінна zi, i = 1, …, 4, автомат видає вихідний сигнал w0 (очікування прийому кортежу вхідних змінних).
65
|
Таблиця 25 – Варіативне задання видалень |
|
|
|||
|
|
|
|
|
|
|
№ |
|
Змінні zi вхідного алфавіту, що |
|
|
№ |
Змінні zi вхідного алфавіту, що |
вар. |
|
видаляються |
|
|
вар. |
видаляються |
1 |
|
z1, z4, z6, z7, z8, z10, z11, z12 |
|
|
19 |
z3, z4, z7, z8, z9, z10, z11, z12 |
2 |
|
z1, z2, z7, z8, z9, z10, z11, z12 |
|
|
20 |
z2, z3, z5, z6, z9, z10, z11, z12 |
3 |
|
z1, z2, z4, z5, z7, z8, z11, z12 |
|
|
21 |
z2, z4, z5, z6, z9, z10, z11, z12 |
4 |
|
z1, z2, z5, z6, z7, z8, z10, z11 |
|
|
22 |
z2, z3, z6, z7, z9, z10, z11, z12 |
5 |
|
z1, z4, z3, z5, z7, z9, z10, z12 |
|
|
23 |
z1, z4, z5, z6, z7, z10, z11, z12 |
6 |
|
z2, z3, z4, z6, z7, z8, z9, z10 |
|
|
24 |
z1, z2, z5, z6, z9, z10, z11, z12 |
7 |
|
z2, z3, z5, z6, z7, z8, z9, z12 |
|
|
25 |
z1, z2, z4, z5, z8, z10, z11, z12 |
8 |
|
z1, z3, z4, z6, z7, z8, z9, z10 |
|
|
26 |
z1, z2, z7, z8, z9, z10, z11, z12 |
9 |
|
z1, z3, z4, z5, z7, z8, z9, z12 |
|
|
27 |
z1, z3, z5, z6, z7, z10, z11, z12 |
10 |
|
z2, z4, z5, z6, z8, z9, z10, z12 |
|
|
28 |
z1, z3, z6, z7, z8, z10, z11, z12 |
11 |
|
z2, z3, z4, z6, z7, z8, z11, z12 |
|
|
29 |
z1, z2, z6, z7, z8, z10, z11, z12 |
12 |
|
z2, z3, z4, z7, z8, z9, z10, z11 |
|
|
30 |
z1, z2, z4, z5, z8, z9, z10, z12 |
13 |
|
z1, z2, z3, z6, z7, z8, z9, z11 |
|
|
31 |
z2, z3, z4, z5, z8, z9, z10, z11 |
14 |
|
z1, z2, z3, z5, z7, z8, z9, z11 |
|
|
32 |
z2, z3, z4, z7, z8, z9, z10, z12 |
15 |
|
z1, z2, z3, z4, z7, z8, z9, z10 |
|
|
33 |
z1, z2, z3, z8, z9, z10, z11, z12 |
16 |
|
z4, z5, z6, z8, z9, z10, z11, z12 |
|
|
34 |
z5, z6, z7, z8, z9, z10, z11, z12 |
17 |
|
z1, z2, z3, z4, z5, z10, z11, z12 |
|
|
35 |
z2, z3, z5, z6, z8, z9, z11, z12 |
18 |
|
z2, z3, z4, z5, z7, z8, z9, z10 |
|
|
36 |
z1, z6, z7, z8, z9, z10, z11, z12 |
Нагадаємо основні властивості абстрактного автомата Мілі. Перехід від поточного такту автоматного часу до наступного такту і зміна його стану відбуваються одночасно. В автоматі Мілі початок кожного такту t автоматного часу (t – номер такту) зазначається поточними станом автомата
після цього ідентифікується вхідна змінна і видається сигнал виходу на поточному такті та визначається стан автомата на наступному такті:
w(t) = (q(t), z(t)) , q(t +1)= (q(t), z(t)).
Наслідком такого алгоритму діяльності є те, що реакція автомата на ідентифіковану вхідну змінну z (t) проявляється без запізнення на тому самому (t-му) такті.
Завдання 3
На підставі базової поміченої таблиці переходів автомата Мура (табл. 26) побудувати варіативно задану таблицю переходів методом видалення стовпців згідно варіанта (табл. 27).
У верхньому рядку таблиці 27 зазначені змінні zi алфавіту входу, які потрібно видалити, після цього пзвести індексацію залишених змінних zi до вигляду послідовності чисел натурального ряду від 1 до 4. Внаслідок буде одержано задану таблицю переходів автомата, після цього потрібно виконати наступне:
1)побудувати орграф заданого автомата Мура;
2)побудувати орграф автомата Мілі, еквівалентного автомата Мура;
3)визначити реакцію автоматів Мура та Мілі на вхідну послідовність
Р (t) = z1 z3 z2 z4 z3 z1 z1 z2 z4 z3,
взявши стан q0 за початковий.
66
Таблиця 26 – Базова таблиця переходів автомата Мура
z(t) |
z1 |
z2 |
z3 |
z4 |
z5 |
z6 |
z7 |
z8 |
z9 |
z10 |
z11 |
z12 |
|
||||||||||||
w(t), q(t) |
|
|
|
|
|
|
|
|
|
|
|
|
|
w0, q0 |
q1 |
q3 |
q2 |
q |
4 |
q |
4 |
q0 |
q2 |
q1 |
q |
2 |
q |
4 |
q |
2 |
q2 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
w1, q1 |
q |
2 |
q |
4 |
q1 |
q0 |
q |
4 |
q3 |
q0 |
q3 |
q3 |
q2 |
q |
4 |
q0 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
w2, q2 |
q0 |
q0 |
q2 |
q3 |
q2 |
q1 |
q0 |
q2 |
q0 |
q2 |
q1 |
q3 |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
w3, q3 |
q3 |
q0 |
q3 |
q2 |
q1 |
q |
4 |
q |
4 |
q2 |
q1 |
q3 |
q |
4 |
q0 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
w4, q4 |
q |
4 |
q0 |
q |
4 |
q0 |
q2 |
q3 |
q0 |
q3 |
q2 |
q1 |
q2 |
q |
4 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
Таблиця 27 – Варіативне задання видалень |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
№ |
|
Змінні zi вхідного алфавіту, що |
|
|
|
№ |
|
|
|
Змінні zi вхідного алфавіту, що |
||||||||||||||||
|
вар. |
|
|
|
видаляються |
|
|
|
|
|
|
вар. |
|
|
|
|
видаляються |
|
|
|
|
||||||
|
1 |
|
z1, z3, z6, z7, z8, z10, z11, z12 |
|
|
|
|
|
|
19 |
|
|
z2, z4, z5, z6, z8, z9, z10, z12 |
|
|
|
|
||||||||||
|
2 |
|
z1, z2, z6, z7, z8, z10, z11, z12 |
|
|
|
|
|
|
20 |
|
|
z2, z3, z4, z6, z7, z8, z11, z12 |
|
|
|
|
||||||||||
|
3 |
|
z1, z2, z4, z5, z8, z9, z10, z12 |
|
|
|
|
|
|
21 |
|
|
z2, z3, z4, z7, z8, z9, z10, z11 |
|
|
|
|
||||||||||
|
4 |
|
z2, z3, z4, z5, z8, z9, z10, z11 |
|
|
|
|
|
|
22 |
|
|
z1, z2, z3, z6, z7, z8, z9, z11 |
|
|
|
|
||||||||||
|
5 |
|
z2, z3, z4, z7, z8, z9, z10, z12 |
|
|
|
|
|
|
23 |
|
|
z1, z2, z3, z5, z7, z8, z9, z11 |
|
|
|
|
||||||||||
|
6 |
|
z1, z2, z3, z8, z9, z10, z11, z12 |
|
|
|
|
|
|
24 |
|
|
z1, z2, z3, z4, z7, z8, z9, z10 |
|
|
|
|
||||||||||
|
7 |
|
z5, z6, z7, z8, z9, z10, z11, z12 |
|
|
|
|
|
|
25 |
|
|
z4, z5, z6, z8, z9, z10, z11, z12 |
|
|
|
|
||||||||||
|
8 |
|
z2, z3, z5, z6, z8, z9, z11, z12 |
|
|
|
|
|
|
26 |
|
|
z1, z2, z3, z4, z5, z10, z11, z12 |
|
|
|
|
||||||||||
|
9 |
|
z1, z6, z7, z8, z9, z10, z11, z12 |
|
|
|
|
|
|
27 |
|
|
z2, z3, z4, z5, z7, z8, z9, z10 |
|
|
|
|
||||||||||
|
10 |
|
z3, z4, z7, z8, z9, z10, z11, z12 |
|
|
|
|
|
|
28 |
|
|
z1, z4, z6, z7, z8, z10, z11, z12 |
|
|
|
|
||||||||||
|
11 |
|
z2, z3, z5, z6, z9, z10, z11, z12 |
|
|
|
|
|
|
29 |
|
|
z1, z2, z7, z8, z9, z10, z11, z12 |
|
|
|
|
||||||||||
|
12 |
|
z2, z4, z5, z6, z9, z10, z11, z12 |
|
|
|
|
|
|
30 |
|
|
z1, z2, z4, z5, z7, z8, z11, z12 |
|
|
|
|
||||||||||
|
13 |
|
z2, z3, z6, z7, z9, z10, z11, z12 |
|
|
|
|
|
|
31 |
|
|
z1, z2, z5, z6, z7, z8, z10, z11 |
|
|
|
|
||||||||||
|
14 |
|
z1, z4, z5, z6, z7, z10, z11, z12 |
|
|
|
|
|
|
32 |
|
|
z1, z4, z3, z5, z7, z9, z10, z12 |
|
|
|
|
||||||||||
|
15 |
|
z1, z2, z5, z6, z9, z10, z11, z12 |
|
|
|
|
|
|
33 |
|
|
z2, z3, z4, z6, z7, z8, z9, z10 |
|
|
|
|
||||||||||
|
16 |
|
z1, z2, z4, z5, z8, z10, z11, z12 |
|
|
|
|
|
|
34 |
|
|
z2, z3, z5, z6, z7, z8, z9, z12 |
|
|
|
|
||||||||||
|
17 |
|
z1, z2, z7, z8, z9, z10, z11, z12 |
|
|
|
|
|
|
35 |
|
|
z1, z3, z4, z6, z7, z8, z9, z10 |
|
|
|
|
||||||||||
|
18 |
|
z1, z3, z5, z6, z7, z10, z11, z12 |
|
|
|
|
|
|
36 |
|
|
z1, z3, z4, z5, z7, z8, z9, z12 |
|
|
|
|
||||||||||
Нагадаємо, що в автоматі Мура початок кожного такту t автоматного часу (t – номер такту) зазначається поточним станом і сигналом на виході автомата
q(t)= (q(t −1), z(t −1)), w(t) = (q(t)),
після цього ідентифікується вхідна змінна і визначається стан автомата на наступному такті:
q(t +1)= (q(t), z(t)).
Наслідком такого алгоритму діяльності є те, що реакція автомата на ідентифіковану вхідну змінну z (t) проявляється із запізненням на один такт у вигляді сигналу на виході
w(t +1) = (q(t +1)) .
67
В автоматі Мілі початок кожного такту t автоматного часу (t – номер такту) зазначається поточним станом автомата
q(t)= (q(t −1), z(t −1)),
після цього ідентифікується вхідна змінна і видається сигнал виходу на поточному такті та визначається стан автомата на наступному такті:
w(t) = (q(t), z(t)) , q(t +1)= (q(t), z(t)).
Наслідком такого алгоритму діяльності є те, що реакція автомата на ідентифіковану вхідну змінну z (t) проявляється без запізнення на тому самому (t-му) такті.
Два автомати, що мають однакові вхідні та вихідні алфавіти, називаються еквівалентними, якщо вони, починаючи з того самого початкового стану, на будь-які однакові вхідні послідовності відповідають однаковими вихідними послідовностями. Іншими словами, два автомати є еквівалентними, якщо після установки в початковий стан їх реакції на будь-яке вхідне слово збігаються. Водночас кількість їх внутрішніх станів може бути різною.
|
|
|
|
|
Завдання 4 |
|
|
|
|
|
||
|
На підставі базової таблиці переходів-виходів автомата Мілі (табл. 28) побудувати |
|||||||||||
варіативно задану таблицю переходів-виходів методом видалення стовпців згідно варіанта |
||||||||||||
(табл. 29). |
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблиця 28 – Базова таблиця переходів-виходів автомата Мілі |
|
|
|
||||||||
z(t) |
|
|
|
|
|
|
|
|
|
|
|
|
q(t) |
z1 |
z2 |
z3 |
z4 |
z5 |
z6 |
z7 |
z8 |
z9 |
z10 |
z11 |
z12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
q1 |
q2 |
q2 |
q0 |
q2 |
q0 |
q2 |
q1 |
q2 |
q1 |
q2 |
q2 |
q0 |
w3 |
w |
w |
w |
w3 |
w1 |
w3 |
w2 |
w |
w2 |
w |
w3 |
|
||||||||||||
|
|
2 |
1 |
3 |
|
|
|
|
1 |
|
2 |
|
|
q2 |
q2 |
q1 |
q0 |
q2 |
q1 |
q0 |
q2 |
q1 |
q2 |
q0 |
q0 |
q1 |
w |
w3 |
w1 |
w2 |
w |
w1 |
w2 |
w |
w1 |
w2 |
w1 |
w |
|
||||||||||||
|
2 |
|
|
|
3 |
|
|
3 |
|
|
|
3 |
|
q0 |
q0 |
q2 |
q1 |
q2 |
q1 |
q0 |
q2 |
q0 |
q2 |
q1 |
q0 |
q2 |
w1 |
w |
w3 |
w1 |
w1 |
w3 |
w |
w3 |
w1 |
w1 |
w3 |
w1 |
|
||||||||||||
|
|
3 |
|
|
|
|
3 |
|
|
|
|
|
У верхньому рядку таблиці 29 вказані змінні zi вхідного алфавіту, які необхідно видалити, після цього звести індексацію залишених змінних zi до вигляду послідовності чисел натурального ряду від 1 до 3. Внаслідок буде одержано задану таблицю переходіввиходів автомата, після цього потрібно виконати наступне:
1)побудувати орграф заданого автомата Мілі;
2)побудувати орграф автомата Мура, еквівалентного автомату Мілі;
3)перевірити еквівалентність автоматів Мілі та Мура методом аналізу реакції автоматів на вхідне слово
р (t) = z1 z2 z2 z4 z3 z1 z4 z2 z4 z3,
взявши за початковий стан q0 із сигналом на виході w1 (або іншим, що для початкового стану неістотно).
68
|
Таблиця 29 – Варіативне задання видалень |
|
|
|||
|
|
|
|
|
|
|
№ |
|
Змінні zi вхідного алфавіту, що |
|
|
№ |
Змінні zi вхідного алфавіту, що |
вар. |
|
видаляються |
|
|
вар. |
видаляються |
1 |
|
z2,z3, z4, z5, z6, z8, z9, z10, z12 |
|
|
19 |
z1, z3, z6, z7, z8, z9, z10, z11, z12 |
2 |
|
z2, z3, z4, z6, z7, z8, z10, z11, z12 |
|
|
20 |
z1, z2, z3, z6, z7, z8, z10, z11, z12 |
3 |
|
z2, z3, z4, z6, z7, z8, z9, z10, z11 |
|
|
21 |
z1, z2, z4, z5, z6, z8, z9, z10, z12 |
4 |
|
z1, z2, z3, z6, z7, z8, z9, z11, z12 |
|
|
22 |
z2, z3, z4, z5, z8, z9, z10, z11, z12 |
5 |
|
z1, z2, z3, z5, z7, z8, z9, z10, z11 |
|
|
23 |
z2, z3, z4, z5, z7, z8, z9, z10, z12 |
6 |
|
z1, z2, z3, z4, z7, z8, z9, z10, z12 |
|
|
24 |
z1, z2, z3, z5, z8, z9, z10, z11, z12 |
7 |
|
z1, z4, z5, z6, z8, z9, z10, z11, z12 |
|
|
25 |
z2, z3, z5, z6, z7, z8, z9, z10, z11 |
8 |
|
z1, z2, z3, z4, z5, z9, z10, z11, z12 |
|
|
26 |
z2, z3, z5, z6, z8, z9, z10, z11, z12 |
9 |
|
z1, z2, z3, z4, z5, z7, z8, z9, z10 |
|
|
27 |
z1, z3, z6, z7, z8, z9, z10, z11, z12 |
10 |
|
z1, z2, z4, z5, z6, z7, z8, z10, z11 |
|
|
28 |
z2, z3, z4, z7, z8, z9, z10, z11, z12 |
11 |
|
z1, z2, z5, z7, z8, z9, z10, z11, z12 |
|
|
29 |
z1, z2, z3, z5, z6, z9, z10, z11, z12 |
12 |
|
z1, z2, z4, z5, z6, z7, z8, z11, z12 |
|
|
30 |
z2, z4, z5, z6, z8, z9, z10, z11, z12 |
13 |
|
z1, z2, z3, z5, z6, z7, z8, z10, z11 |
|
|
31 |
z2, z3, z4, z6, z7, z9, z10, z11, z12 |
14 |
|
z1, z3, z4,z5, z7, z8, z9, z10, z12 |
|
|
32 |
z1, z4, z5, z6, z7, z8, z10, z11, z12 |
15 |
|
z2, z3, z4, z6, z7, z8, z9, z10, z12 |
|
|
33 |
z1, z2, z3, z5, z6, z9, z10, z11, z12 |
16 |
|
z1, z2, z3, z5, z6, z7, z8, z9, z12 |
|
|
34 |
z1, z2, z4, z5, z6, z8, z10, z11, z12 |
17 |
|
z1, z3, z4, z6, z7, z8, z9, z10, z12 |
|
|
35 |
z1, z2, z3, z7, z8, z9, z10, z11, z12 |
18 |
|
z1, z3, z4, z5, z7, z8, z9, z11, z12 |
|
|
36 |
z1, z3, z5, z6, z7, z8, z10, z11, z12 |
4.5 Розділ 5. Структурний синтез автоматів. Постановка завдань
Завдання1
На підставі базової поміченої таблиці переходів автомата Мура (табл. 30) побудувати варіативно задану таблицю переходів методом видалення стовпців згідно варіанту (табл. 31).
Таблиця 30 – Базова таблиця переходів автомата Мура
z(t) |
z1 |
z2 |
z3 |
z4 |
z5 |
z6 |
z7 |
z8 |
z9 |
z10 |
z11 |
z12 |
z13 |
|||
|
|
|
||||||||||||||
w(t), q(t) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
w0, q0 |
q1 |
q3 |
q2 |
q1 |
q3 |
q0 |
q2 |
q1 |
q |
2 |
q0 |
q |
2 |
q2 |
q0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
w1, q1 |
q |
2 |
q1 |
q1 |
q0 |
q0 |
q3 |
q3 |
q3 |
q3 |
q2 |
q0 |
q0 |
q0 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
w2, q2 |
q0 |
q0 |
q0 |
q3 |
q2 |
q1 |
q0 |
q2 |
q0 |
q1 |
q1 |
q3 |
q0 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
w3, q3 |
q3 |
q2 |
q3 |
q2 |
q1 |
q2 |
q1 |
q0 |
q1 |
q3 |
q3 |
q1 |
q0 |
|||
69
|
Таблиця 31 – Варіативне задання видалень |
|
|
|||
|
|
|
|
|
|
|
№ |
|
Змінні zi вхідного алфавіту, |
|
|
№ |
Змінні zi вхідного алфавіту, |
вар. |
|
що видаляються |
|
|
вар. |
що видаляються |
1 |
|
z1, z3, z6, z7, z8, z10, z11, z12 |
|
|
19 |
z2, z4, z5, z6, z8, z9, z10, z12 |
2 |
|
z1, z2, z6, z7, z8, z10, z11, z12 |
|
|
20 |
z2, z3, z4, z6, z7, z8, z11, z12 |
3 |
|
z1, z2, z4, z5, z8, z9, z10, z12 |
|
|
21 |
z2, z3, z4, z7, z8, z9, z10, z11 |
4 |
|
z2, z3, z4, z5, z8, z9, z10, z11 |
|
|
22 |
z1, z2, z3, z6, z7, z8, z9, z11 |
5 |
|
z2, z3, z4, z7, z8, z9, z10, z12 |
|
|
23 |
z1, z2, z3, z5, z7, z8, z9, z11 |
6 |
|
z1, z2, z3, z8, z9, z10, z11, z12 |
|
|
24 |
z1, z2, z3, z4, z7, z8, z9, z10 |
7 |
|
z5, z6, z7, z8, z9, z10, z11, z12 |
|
|
25 |
z4, z5, z6, z8, z9, z10, z11, z12 |
8 |
|
z2, z3, z5, z6, z8, z9, z11, z12 |
|
|
26 |
z1, z2, z3, z4, z5, z10, z11, z12 |
9 |
|
z1, z6, z7, z8, z9, z10, z11, z12 |
|
|
27 |
z2, z3, z4, z5, z7, z8, z9, z10 |
10 |
|
z3, z4, z7, z8, z9, z10, z11, z12 |
|
|
28 |
z1, z4, z6, z7, z8, z10, z11, z12 |
11 |
|
z2, z3, z5, z6, z9, z10, z11, z12 |
|
|
29 |
z1, z2, z7, z8, z9, z10, z11, z12 |
12 |
|
z2, z4, z5, z6, z9, z10, z11, z12 |
|
|
30 |
z1, z2, z4, z5, z7, z8, z11, z12 |
13 |
|
z2, z3, z6, z7, z9, z10, z11, z12 |
|
|
31 |
z1, z2, z5, z6, z7, z8, z10, z11 |
14 |
|
z1, z4, z5, z6, z7, z10, z11, z12 |
|
|
32 |
z1, z4, z3, z5, z7, z9, z10, z12 |
15 |
|
z1, z2, z5, z6, z9, z10, z11, z12 |
|
|
33 |
z2, z3, z4, z6, z7, z8, z9, z10 |
16 |
|
z1, z2, z4, z5, z8, z10, z11, z12 |
|
|
34 |
z2, z3, z5, z6, z7, z8, z9, z12 |
17 |
|
z1, z2, z7, z8, z9, z10, z11, z12 |
|
|
35 |
z1, z3, z4, z6, z7, z8, z9, z10 |
18 |
|
z1, z3, z5, z6, z7, z10, z11, z12 |
|
|
36 |
z1, z3, z4, z5, z7, z8, z9, z12 |
У таблиці 30 структурні змінні z1 ‒ z12 є 4-мірними кортежами змінних x1, x2, x3, x4 входу автомата:
z 1 = (x1 x2 x3 x4 ), z2 = ( x1 x2 x3 x4 ), z3 = ( x1 x2 x3 x4 ), z4 = ( x1 x2 x3 x4), z5 = (x1x2 x3 x4 ),
z6 = ( x1 x2x3 x4 ), z7 = ( x1 x2 x3x4), z8 = (x1 x2 x3 x4), z9 = ( x1 x2 x3 x4), z10 = (x1 x2 x3 x4 ), z11 = (x1x2x3 x4 ), z12 = (x1 x2 x3x4), z13 = ( x1 x2 x3 x4 ).
Структурні змінні w0 ‒ w3 є 4-мірними кортежами змінних y1, y2, y3, y4 виходу автомата: w0 = (y1 y2 y3 y4 ), w1 = ( y1 y2 y3 y4 ), w2 = ( y1 y2 y3 y4 ), w3 = ( y1 y2 y3 y4).
Кортежі змінних zi, і = 1, …, 13 та wi, і = 1, …, 4 є конституентами одиниці, що являють собою набори змінних входу та виходу, в яких змінні без заперечення та із запереченням мають значення відповідно 1 та 0.
Автомат є ініціальним. Ініціальність забезпечується тим, що відсутність сигналів на всіх каналах входу (x1 = x2 = x3 = x4 = 0 до початку і по закінченні роботи автомата)
зазначається змінною z13 = ( x1 x2 x3 x4 ). У початковому стані q0 автомат сприймає вхідний
сигнал z13 = (0000) та залишається у цьому стані до пяви на вході інших сигналів. Перехід автомата із будь-якого стану в стан q0 за змінною z13 означає закінчення його роботи з поверненням у початковий стан q0.
У верхньому рядку таблиці 31 зазначені змінні zi алфавіту входу, які необхідно видалити. Внаслідок буде одержано варіативно задану помічену таблицю переходів структурного автомата Мура, після цього потрібно виконати наступне:
1)за таблицею переходів побудувати орграф автомата Мура;
2)визначити необхідну кількість тригерів як елементів пам’яті, вибрати тип тригерів та виконати кодування станів автомата;
3)накреслити функціональну схему автомата Мура з використанням тригерів вибраного типу та пояснити процес його функціонування;
4)розробити комбінаційні схеми у складі автомата Мура.
70