Условия сохраняемости (lossiness) информации
Машина, которая не сохраняет информацию называется не сохраняющей (lossy) информацию.
Простой пример не сохраняющей машины – это такая, в которой для некоторого состояния Si
и двух отличных входных символов Ip и Iq, Ip- и Iq-преемники и соответствующие им выходы идентичны. Ясно, что в таком случае знание выхода, начального и конечного состояния не достаточно, чтобы определить, какой из Ip ,Iq были поданы на вход машины.
Рис. 3
Потеря информации происходит тогда, когда существуют два состояния Si и Sj, которые могут быть достигнуты от одного и того же состояния Sс, которые могут быть достигнуты при различных входных последовательностях, которые переводят машину в одно и то же состояние Sf
и генерируют одинаковые выходные последовательности (см. Рис. 3).
Пример. Пусть задана машина, таблица переходов которой показана на Рис. 4а. Как видно из Рис. 4b, эта машина относится к типу несохранающих информацию. В этом случае две различные входные последовательности (01 и 10) переводят машину из состояния А в В и производят одинаковую выходную последовательность.
Приведенное выше показывает, что прежде, чем планировать тестирующий эксперимент, необходимо проверить, является ли она информацию-сохраняющей. Необходимо определить, для некоторого состояния, не возникает ли ситуация, показанная на Рис. 3. Прежде чем рассматривать построение теста на информационную сохранность, определим порядок информационной сохранности.
|
PS |
NS,z | ||||
|
x=0 |
x=1 | ||||
|
A |
A,0 |
B,0 | |||
|
B |
B,0 |
A,1 | |||
a)
b)
Рис. 4
