Тест на информацию сохраняемость
Перейдем к получению теста, позволяющего определить, является ли данная машина информацию сохраняющей и каков ее ?-порядок, если она конечна. Прежде, чем перейти к тестирующей процедуре, введем некоторые термины.
Определение. 6 Два состояния Si
и Sj будем называть сочетаемыми по выходу, если существует некоторое состояние Sp
такое, что оба Si и Sj являются его Ок-преемниками или если существует сочетаемая пара SrSt
такая, что SiSj
имеют свои Ок-преемники. В таком случае будем говорить, что из сочетаемости (SiSj) вытекает сочетаемость (SrSt).
Первый шаг тестирующей процедуры есть проверка каждой строки таблицы для выявления двух идентичных переходов имеющих одинаковые значения выходов. Если нет идентичных вхождений, следующий шаг – это построение таблицы переходов по выходам.
Тестирующая таблица (информацию сохраняющая) состоит из двух частей. Верхняя часть содержит выходные
| PS | NS,z | ||||
| x=0 | x=1 | ||||
| A | A,1 | C,1 | |||
| B | E,0 | B,1 | |||
| C | D,0 | A,0 | |||
| D | C,0 | B,0 | |||
| E | B,1 | A,0 |
преемники, а нижняя половина строится следующим образом: в каждой строке записывается сочетание из верхней таблицы (AC,AD и BC). Преемники в этой таблице строятся обычным способом, и состоят из сочетаемых пар. Если при этом появляется очередная сочетаемая пара (например, АЕ и DЕ в строке ВС), которую записывают в новую строку, и т.д..
На Рис. 5а приведен пример Машины, на котором рассмотрим описанную процедуру.
Таблица выходных переходов показана в верхней части таблицы Рис. 5b. (AC) является сочетаемой парой (А и С имеют одинаковые значения выходов), по этой причине эта пара записывается в нижнюю часть таблицы. Остальные строки заполняются аналогично.
Сформулируем необходимые и достаточные условия существования информацию сохраняющей машины.
Утверждение 3 Машина является информацию сохраняющей, если и только если тестирующая таблица не содержит сочетаемые пары с повторяющимися компонентами.
Тестирующий граф (для информационной сохраняемости) есть направленный граф, в котором:
направляется из вершины SiSj
в вершину SpSq
(где p?q), если и только если (SpSq) находится в строке SiSj.
Пример тестирующего графа приведен на Рис. 5с. Как видно из графа, машина является информацию сохраняющей.
Прежде, чем определить ?-порядок, рассмотрим утверждение:
Утверждение 4. Машина есть информацию сохраняющая порядка µ=l+2, если тестирующий граф свободен от циклов и длина наибольшего пути графа равна l.
Доказательство.
Допустим, что машина М – информацию сохраняющая. Примем, что граф не имеет цикла. Очевидно, что каждая совместимая пара достижима из некоторого состояния М при паре соответствующих входных последовательностей, которые выдают идентичные выходные последовательности. Поэтому мы можем найти пару различных входных последовательностей, которые переводят М в состоянии SiSj, при выработке идентичных выходных последовательностей. Если мы теперь осмотрим выходные символы, которые производит машина, до тех пор, пока не пройдем все сочетаемые пары в цикле, то мы обнаружим, что М возвратится в состояние SiSj
без любой дополнительной информации, чтобы получить первый входной символ. И так как этот цикл может повторяться много раз, при желании, мы можем создать пару произвольно длинных входных последовательностей, которые начинаются в некотором состоянии М и отличаются первыми символами, но вырабатывают одинаковые выходные последовательности. Таким образом, М не является информацию сохраняющей конечного порядка
Из «Утверждение 4» следует, что если М – информацию сохраняющая машина порядка µ, то µ?1+n(n-1)/2.
При µ=1 отсутствуют сопоставимые пары (см. Table 5), в то время, как при µ=2 обнаруживает отсутствие дуг. Если вернуться к графу на Рис. 5с то мы увидим, что он имеет цикл, поэтому машина не информацию сохраняющая конечного порядка.
Пример.
Еще один пример построения теста показан на Рис. 6. Как видно из Рис. 6с, тестирующий граф не имеет цикла и, так как l=1, то µ=3.
|
NS,z |
PS |
|
|
z=1 |
z=0 |
|
|
B,0 |
A,0 |
A |
|
D,0 |
C,0 |
B |
|
C,1 |
D,1 |
C |
|
A,1 |
B,1 |
D |
(BC)(BD)
(BC)(BD)
