Page 81 - 4128

так зване сусіднє кодування станів автомата, при якому умова
відсутності гонок завжди виконана. При сусідньому кодуванні
будь-які два, стани зв'язані дугою на графі автомата кодуються
наборами, відмінними станами лише одного елементу пам'яті.
Сусіднє кодування не завжди можливе. Граф автомата,
допускаюче сусіднє кодування, повинен задовольняти ряду вимог,
а саме:
1 у графі автомата не повинно бути циклів з непарним
числом вершин;
2 двох сусідніх станів другого порядку не повинне
мати більше двох станів, що лежать між ними.
3

а 2
а 1

а 2 а 6 а 1 а 3
а 1
а 7

а 3 а 5 а 2 а 3 а 4

а 4 а 5

а) б)

Рисунок 4.4 – Графи автоматів, що допускають (а) і не
допускають (б) сусіднє кодування

80