Домашка № 19.
Противогоночное кодирование автоматов.
Таблица переходов:
|
0q0 |
Qq1 |
2q2 |
2q3 |
4q4 |
5q5 |
6q6 |
7q7 |
8q8 |
9q9 |
|
|
XX0 |
Qq0 |
2q2 |
2q2 |
4q4 |
4q4 |
0q0 |
6q6 |
8q8 |
8q8 |
9q0 |
|
XX1 |
0q0 |
1q1 |
3q3 |
3q3 |
0q0 |
0q0 |
7q7 |
7q7 |
9q9 |
9q9 |
|
XX2 |
6q6 |
2q2 |
2q2 |
4q4 |
4q4 |
5q5 |
6q6 |
8q8 |
8q8 |
5q5 |
|
XX3 |
1q1 |
1q1 |
3q3 |
4q3 |
5q5 |
5q5 |
7q7 |
7q7 |
9q9 |
9q9 |
Таблица выходов:
|
0q0 |
Qq1 |
2q2 |
2q3 |
4q4 |
5q5 |
6q6 |
7q7 |
8q8 |
9q9 |
|
|
XX0 |
Yy0 |
Yy0 |
Yy0 |
1y1 |
Yy1 |
Yy0 |
Yy0 |
Yy1 |
Yy1 |
Yy1 |
|
XX1 |
Yy0 |
Yy0 |
Yy1 |
Yy1 |
Yy0 |
Yy0 |
Yy0 |
Yy0 |
Yy1 |
Yy1 |
|
XX2 |
Yy0 |
Yy0 |
0y0 |
Yy1 |
Yy1 |
Yy0 |
Yy0 |
Yy1 |
Yy1 |
Yy1 |
|
XX3 |
Yy0 |
Yy0 |
Yy1 |
Yy1 |
Yy0 |
Yy0 |
Yy0 |
Y0 |
Yy1 |
Yy1 |
Граф автомата:
 |
В графе есть контуры нечётной длины, и мы не можем провести противогоночное кодирование , не изменяя таблицу переходов. Кроме того, у состояния q0 есть пять соседних состояний, значит для кодирования состояний автомата соседним кодом нужно не менее пяти разрядов. Для кодирования же десяти состояний нужно четыре разряда. Поэтому мы выберем противогоночное кодирование с устранением только критических состязаний.
Переходы:
|
|
|
|
|
|
|
|
|
|
|
|
(q1,q1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(q6,q6) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Теперь будем обозначать q0 как 0, q1 как1 и т.д.
Таблица пар состояний, подлежащих развязыванию:
|
№ |
|
|
|
|
|
1 |
(00),(12) |
(00),(11) |
(06),(12) |
(01),(23) |
|
2 |
(00),(22) |
(00),(23) |
(06),(22) |
(01),(33) |
|
3 |
(00),(34) |
(00),(33) |
(06),(34) |
(01),(45) |
|
4 |
(00),(44) |
(00),(67) |
(06),(44) |
(01),(55) |
|
5 |
(00),(66) |
(00),(77) |
(06),(55) |
(01),(67) |
|
6 |
(00),(78) |
(00),(89) |
(06),(78) |
(01),(77) |
|
7 |
(00),(88) |
(00),(99) |
(06),(88) |
(01),(89) |
|
8 |
(12),(34) |
(11),(23) |
(06),(95) |
(01),(99) |
|
9 |
(12),(44) |
(11),(33) |
(12),(34) |
(11),(23) |
|
10 |
(12),(50) |
(11),(40) |
(12),(44) |
(11),(33) |
|
11 |
(12),(66) |
(11),(50) |
(12),(55) |
(11),(45) |
|
12 |
(12),(78) |
(11),(67) |
(12),(66) |
(11),(55) |
|
13 |
(12),(88) |
(11),(77) |
(12),(78) |
(11),(67) |
|
14 |
(12),(90) |
(11),(89) |
(12),(88) |
(11),(77) |
|
15 |
(22),(34) |
(11),(99) |
(12),(95) |
(11),(89) |
|
№ |
|
|
|
|
|
16 |
(22),(44) |
(23),(40) |
(22),(34) |
(11),(99) |
|
17 |
(22),(50) |
(23),(50) |
(22),(44) |
(23),(45) |
|
18 |
(22),(66) |
(23),(67) |
(22),(55) |
(23),(55) |
|
19 |
(22),(78) |
(23),(77) |
(22),(66) |
(23),(67) |
|
20 |
(22),(88) |
(23),(89) |
(22),(78) |
(23),(77) |
|
21 |
(22),(90) |
(23),(99) |
(22),(78) |
(23),(89) |
|
22 |
(34),(50) |
(33),(40) |
(22),(95) |
(23),(99) |
|
23 |
(34),(66) |
(33),(50) |
(34),(55) |
(33),(45) |
|
24 |
(34),(78) |
(33),(67) |
(34),(66) |
(33),(55) |
|
25 |
(34),(88) |
(33),(77) |
(34),(78) |
(33),(67) |
|
26 |
(34),(90) |
(33),(89) |
(34),(88) |
(33),(77) |
|
27 |
(44),(50) |
(33),(99) |
(34),(95) |
(33),(89) |
|
28 |
(44),(66) |
(40),(67) |
(44),(55) |
(33),(99) |
|
29 |
(44),(78) |
(40),(77) |
(44),(66) |
(45),(67) |
|
30 |
(44),(88) |
(40),(89) |
(44),(78) |
(45),(77) |
|
31 |
(44),(90) |
(40),(99) |
(44),(88) |
(45),(89) |
|
32 |
(50),(66) |
(50),(67) |
(44),(95) |
(45),(99) |
|
33 |
(50),(78) |
(50),(77) |
(55),(66) |
(55),(67) |
|
№ |
|
|
|
|
|
34 |
(50),(88) |
(50),(89) |
(55),(78) |
(55),(77) |
|
35 |
(66),(78) |
(50),(99) |
(55),(88) |
(55),(89) |
|
36 |
(66),(88) |
(67),(89) |
(66),(78) |
(55),(99) |
|
37 |
(66),(90) |
(67),(99) |
(66),(88) |
(67),(89) |
|
38 |
(78),(90) |
(77),(89) |
(66),(95) |
(67),(99) |
|
39 |
(88),(90) |
(77),(99) |
(78),(95) |
(77),(89) |
|
40 |
(88),(95) |
(77),(99) |
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
(по 
)
(по
)
(по
)
(по 
)
(q0,q0)
(q0,q0)
(q0,q6)
(q0,q1)
(q1,q2)
(q1,q2)
(q1,q1)
(q2,q3)
(q3,q4)
(q3,q3)
(q3,q4)
(q3,q3)
(q4,q4)
(q4,q0)
(q4,q5)
(q5,q0)
(q5,q5)
(q5,q5)
(q6,q7)
(q6,q7)
(q7,q8)
(q8,q9)
(q8,q9)
(q9,q9)
(q9,q9)