|
Таблица переходов δ(q,x) | |||||||||||||||||||||
|
q0 |
q1 |
q2 |
q3 |
q4 |
q5 |
||||||||||||||||
X0 |
q0 |
q1 |
q3 |
q3 |
q0 |
q0 |
||||||||||||||||
X1 |
q0 |
q2 |
q2 |
q4 |
q4 |
q0 |
||||||||||||||||
X2 |
q1 |
q1 |
q3 |
q3 |
q5 |
q5 |
||||||||||||||||
X3 |
q2 |
q2 |
q2 |
q4 |
q4 |
q5 |
Таблица выходов λ(q,x)
q0
q1
q2
q3
q4
q5
X0
0
0
1
1
1
0
X1
0
0
0
1
0
0
X2
0
0
1
1
0
0
X3
0
0
0
1
1
0
Минимизация памяти абстрактного автомата
Таблица выходов λ(q,x)
q0
q1
q2
q3
q4
q5
X0
0
0
1
1
1
0
X1
0
0
0
1
0
0
X2
0
0
1
1
0
0
X3
0
0
0
1
1
0
A0
A0
A1
A2
A3
A0
A0 = {q0, q1, q5}
A1 = {q2}
A2 = {q3}
A3 = {q4}
q0
q1
q5
q2
q3
q4
X0
A0
A0
A0
A2
A2
A0
X1
A0
A1
A0
A1
A3
A3
X2
A0
A0
A0
A2
A2
A0
X3
A1
A1
A0
A1
A3
A3
B0
B1
B2
B3
B4
B5
Таким образом, невозможно минимизировать память абстрактного автомата.
Выбор способа противогоночного кодирования
Существует ряд способов противогоночного кодирования, которые можно разбить на две группы:
1. Методы, позволяющие устранить все состязания. Используется “соседнее кодирование”, когда всем соседним внутренним состояниям приписывают соседние кодовые комбинации, отличающиеся значением только 1 разряда.
В случае использования таких методов уменьшается быстродействие, но зато устраняются все состязания.
2. Методы, устраняющие только критические состязания (состязания при которых в дальнейшей работе автомат не переходит из ошибочных состояний в состояние, предусмотренное алгоритмом функционирования)
Для упрощения схемы и увеличения быстродействия устраняем только критические состязания.
Противогоночное кодирование осуществляется путем развязывания пар переходов.
Две пары двоичных наборов длины “l” – (α,β) и (γ,δ) называются развязанными, если i-ый разряд кода принимает одно значение на паре (α,β) и другое на паре (γ,δ)
Противогоночное кодирование состояний автомата
M0
M1
M2
M3
q0, q0
q1, q1
q2, q3
q3, q3
q4, q0
q5, q0
q0, q0
q1, q2
q2, q2
q3, q4
q4, q4
q5, q0
q0, q1
q1, q1
q2, q3
q3, q3
q4, q5
q5, q5
q0, q2
q1, q2
q2, q2
q3, q4
q4, q4
q5, q5
τ1
τ2
τ3
q0
0
0
0
q1
1
0
0
q2
1
1
0
q3
1
1
1
q4
0
1
1
q5
0
0
1
Развязывание пар переходов в массиве М0
1
q0
q0
q1
q1
0
0
1
1
3
q0
q0
q3
q3
0
0
1
1
2
Q0
q0
q2
q3
0
0
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Новости |
Мои настройки |
|
© 2009 Все права защищены.