в Table 2а, соответствует предельному
Машина M2 показанная в Table 2а, соответствует предельному значению µ.
|
PS |
NS,z |
|
|
x=0 |
x=1 |
|
|
A |
B,0 |
D,0 |
|
B |
C,0 |
C,0 |
|
C |
D,0 |
A,0 |
|
D |
D,0 |
A,1 |
|
a) |
0/1
1/1
1/0
A
B
-
-
D
B
C
-
-
C
C
D
-
-
A
D
D
-
A
-
AB
BC
-
-
CD
AC
BD
-
-
AD
AD
BD
-
-
-
BC
CD
-
-
AC
BD
CD
-
-
-
CD
DD
-
-
-
b)
Table 2
Соответствующая тестирующая таблица и граф показаны в Table 2b и Рис. 2, соответственно. Как это видно, тестирующий граф свободен от циклов и максимальный путь, начинающийся в АВ и оканчивающийся в CD, имеет длину 5. Отсюда µ=6. В общем, можно показать, что существует класс машин, для которых µ=(n-1)n/2.
Рис. 2
