Граф переходов
3.Объединение строк таблиц переходов
3.1 Нахождение максимального подмножества совместимых строк (МПСС ТП)
Для составления таблицы покрытий (табл. 2) имеем:
Е22={1,2,3,6,7}
Е213
={3,6,7,12,13} Е412={2,5,8,9,11,12,13}
Е25={3,4,5,6,7} Е44={2,3,4,5,8,9,13} Е33={2,3,4,5,9,10,11,12,13}
Е29={3,6,7,8,9} Е47 ={2,5,6,7,8,9,13} Е36={1,4,5,6,9,10,11,12,13}
Е211={3,6,7,10,11} Е410={1,2,5,8,9,10,13} Е38={4,5,7,8,9,10,11,12,13}
Найдем следующие множества:
Е2,3,4={2,3} Е5,3,4={3,4,5} Е9,3,4={3,9}
Е2,6,4= ø Е5,6,4={4,5} Е9,6,4={9}
Е2,8,4= ø Е5,8,4={4,5} Е9,8,4={8,9}
Е2,3,7={2} Е5,3,7={5} Е9,3,7={9}
Е2,6,7= {6} Е5,6,7={5,6} Е9,6,7={6,9}
Е2,8,7={7} Е5,8,7={5,7} Е9,8,7={7,8,9}
Е2,3,10={2} Е5,3,10={5} Е9,3,10={9}
Е2,6,10= {1} Е5,6,10={5} Е9,6,10={9}
Е2,8,10= ø Е5,8,10={5} Е9,8,10={8,9}
Е2,3,12= {2} Е5,3,12={5} Е9,3,12={9}
Е2,6,12= ø Е5,6,12={5} Е9,6,12={9}
Е2,8,12= ø Е5,8,12={5} Е9,8,12={8,9}
Е11,3,4= {3} Е13,3,4={3,13}
Е11,6,4 = ø Е13,6,4={3,13}
Е11,8,4= ø Е13,8,4=1{3}
Е11,3,7= ø Е13,3,7=1{3}
Е11,6,7= {6} Е13,6,7={ 6,13 }
Е11,8,7={7} Е13,8,7={7,13}
Е11,9,10={10} Е13,3,10={13 }
Е11,6,10={10} Е13,6,10={ 13 }
Е11,8,10={10} Е13,8,10={13}
Е11,3,12={11} Е13,3,12={ 12,13 }
Е11,6,12={11} Е13,6,12={12,13}
Е11,8,12={11} Е13,8,12={12,13}
Максимальные подмножества, обозначенные латинскими буквами:
Е2,3,4={2,3}= A Е11,3,10={10}= К
Е5,3,4={3,4,5}= B Е11,3,12 ={11}= L
Е5,6,7={5,6}= C Е13,3,12={12,13}= М
Е5,8,7={5,7}= D Е2,6,10 ={13 }= N
Е9,8,7={7,8,9}= E
3.2.Составление таблицы покрытий
В табл. 2 представлена составленная таблица покрытий
Таблица 2.Таблица покрытий
S |
A |
B |
C |
D |
E |
К |
L |
М |
N |
1 |
|
|
|
|
|
|
|
|
+ |
2 |
+ |
|
|
|
|
|
|
|
|
3 |
+ |
+ |
|
|
|
|
|
|
|
4 |
|
+ |
|
|
|
|
|
|
|
5 |
|
+ |
+ |
+ |
|
|
|
|
|
6 |
|
|
+ |
|
|
|
|
|
|
7 |
|
|
|
+ |
+ |
|
|
|
|
8 |
|
|
|
|
+ |
|
|
|
|
9 |
|
|
|
|
+ |
|
|
|
|
10 |
|
|
|
|
|
+ |
|
|
|
11 |
|
|
|
|
|
|
+ |
|
|
12 |
|
|
|
|
|
|
|
+ |
|
13 |
|
|
|
|
|
|
|
+ |
|
3.3 Решение задачи покрытия
Для табл. 2 имеем:
Q= A*(А ˅ В)*В*(B ˅ С)*С*Е*Е*Е*K*L*М*N=A*B*C*E*K*L*M*N
3.4 Нахождение минимального множества таблицы покрытия
Объединение строк первичной таблицы переходов w и исключение повторения цифр W’:
W= A*B*C*E*K*L*M*N = {1}{2,3}{3,4,5}{5,6}{7,8,9}{10}{ ø }{2,13}
W’ = {1}{2,3}{4,5}{6}{7,8,9}{10}{11}{12,13}
В табл. 3 приведена минимизированная таблица переходов
Таблица 3. Минимизированная таблица переходов
S |
x1 x2 |
|||
00 |
01 |
10 |
11 |
|
1 |
(1),00 |
2,01 |
6, 00 |
10, 10 |
2,3 |
~ |
(2),01 |
(3),10 |
~ |
4,5 |
1,00 |
(5),10 |
~ |
(4),11 |
6 |
~ |
~ |
(6),00 |
7,01 |
7,8,9 |
1,00 |
(9),00 |
(8),01 |
(7),01 |
10 |
~ |
11,01 |
~ |
(10),10 |
11 |
~ |
(11),01 |
~ |
12,11 |
12,13 |
1,00 |
(13),10 |
~ |
(12),11 |
3.5 Построение минимизированной ТП
Перенумеровав строки минимизированной таблицы переходов, получаем табл. 4.
Таблица 4. Таблица переходов после нумерации
S |
x1 x2 |
|||
00 |
01 |
10 |
11 |
|
1 |
(1),00 |
2,01 |
4, 00 |
6, 10 |
2 |
~ |
(2), 01 |
(2),10 |
~ |
3 |
1,00 |
(3),10 |
~ |
(3), 11 |
4 |
~ |
~ |
(4),00 |
5,01 |
5 |
1,00 |
(5),00 |
(5), 01 |
(5),01 |
6 |
~ |
7,01 |
~ |
(6),10 |
7 |
~ |
(7),01 |
~ |
8,11 |
8 |
1,00 |
(8),10 |
~ |
(8),11 |