E10,2,6,12 = {Ø} E10,2,9,3 = {Ø} E10,2,9,7 = {Ø} E10,2,9,12 = {Ø} E10,2,11,3 = {10} E10,2,11,7 = {10} E10,2,11,12 = {10,11} |
E10,5,6,12 = {Ø} E10,5,9,3 = {Ø} E10,5,9,7 = {Ø} E10,5,9,12 = {Ø} E10,5,11,3 = {10} E10,5,11,7 = {10} E10,5,11,12 = {10,11} |
E10,8,6,12 = {Ø} E10,8,9,3 = {8} E10,8,9,7 = {7,8} E10,8,9,12 = {8} E10,8,11,3 = {10} E10,8,11,7 = {7,10} E10,8,11,12 = {10,11} |
Из полученных множеств исключаются те, которые полностью входят в другое множество. Оставшиеся множества Ei1,i2,i3,i4 являются максимальными подмножествами совместимых строк, они обозначаются латинскими буквами:
E1,2,4,3 = {1,3} = A;
E1,2,6,7 = {1,6} = B;
E1,2,9,12 = {1,9,12} = C;
E1,2,11,12 = {1,11,12} = D;
E1,5,4,3 = {3,4,5} = E;
E1,5,4,12 = {4,5,12} = F;
E1,5,6,7 = {5,6} = G;
E1,5,9,12 = {5,9,12} = H;
E1,5,11,12 = {5,11,12} = I;
E1,8,6,7 = {6,7} = J;
E1,8,9,7 = {7,8,9} = K;
E1,8,9,12 = {8,9,12} = L;
E10,2,6,3 = {2} = M;
E10,2,11,12 = {10,11} = N;
E10,8,11,7 = {7,10} = O.
2.4.2 Составление таблицы покрытий
Столбцы таблицы соответствуют множествам A,B, …, O, а строки – строкам первичной таблицы переходов. На пересечении строки и столбца ставится знак «+», если данная строка таблицы переходов входит в данное подмножество совместимых строк.
Решение задачи покрытия.
Находится минимальное множество столбцов W такое, что каждая строка (состояние) входит хотя бы в одно из них. Для этого составляется алгебраическое выражение Q типа конъюнкция дизъюнкций. Каждая дизъюнкция образуется как дизъюнкция тех столбцов, в которых стоит метка «+» в данной строке (табл. 2).
Таблица 2
Таблица покрытий
S |
А |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
1 |
+ |
+ |
+ |
+ |
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
+ |
|
|
3 |
+ |
|
|
|
+ |
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
+ |
+ |
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
+ |
+ |
+ |
+ |
+ |
|
|
|
|
|
|
6 |
|
+ |
|
|
|
|
+ |
|
|
+ |
|
|
|
|
|