Тестирующая таблица и тестирующий граф
Примем, что существует машина М1, заданная Table 1а.. Мы можем переписать эту таблицу, как показано в верхней половине таблицы Table 1b. В заголовке этой таблицы записаны все сочетания значений входов-выходов. Остальные строки верхней половины таблицы заполняются состояниями, в которые произойдет переход при соответствующем значении входа-выхода. Например, 1-суксессор (наследник) состояния С есть В и соответствующее значение выхода равно 1. Поэтому В вписан в строке С в столбец 1/1 и вписана черточка в столбце 1/0.
В первом столбце нижней части таблицы выписаны все паро-сочетания состояний, которые образованы из состояний верхней части таблицы. Если в строках Si
и Sj в столбце Ik/Ol
в верхней части таблицы есть Sp и Sq,
соответственно, тогда в строке SiSj в нижней части таблицы в столбце Ik/Ol записываем SpSq. Если для некоторой пары состояний Si
и Sj в столбце Ik/Ol
в верхней части таблицы присутствует хотя бы одна черточка, то в строке SiSj
в столбце Ik/Ol следует поставить черточку.
|
PS |
NS,z | ||||
|
x=0 |
x=1 | ||||
|
A |
B,0 |
C,1 | |||
|
B |
D,0 |
C,0 | |||
|
C |
D,0 |
B,1 | |||
|
D |
C,0 |
A,0 | |||
|
a) | |||||
0/0
0/1
1/1
1/0
A
B
-
C
-
B
D
-
-
C
C
D
-
B
-
D
C
-
-
A
AB
BD
-
-
-
AC
BD
-
BC
-
AD
BC
-
-
-
BC
DD
-
-
-
BD
CD
-
-
AC
CD
CD
-
-
-
b)
Table 1
Таблица вида Table 1 называется тестирующей таблицей.
Мы будем называть пару SiSj, как неопределенную пару, и ее преемника SpSq, как предполагаемую пару. Например, пара АС порождает пару BD.
Определим теперь направленный граф G, который будем называть тестирующий граф, который построен следующим способом.
Рис. 1
с вершиной SpSq, где p ? q, если и только если существует SpSq
в строке SiSj
и столбце Ik/Ol
тестирующей таблицы. Стрелку обозначить Ik/Ol.
Тестирующий граф G1 машины M1 (см. Table 1b) показан на Рис. 1
