Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА)
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
»ичительных последовательностей.
Рассмотрим автомат А-3, заданный таблицей переходов-выходов (таблица 3.3). Отличительное и синхронизирующее деревья автомата А-3 приведены на рисунке 3.3a и рисунке 3.3б соответственно. Автомат имеет синхронизирующую последовательность Xs = 11 и две отличительные последовательности X01 = 01 и X02 = 00.
Построим последовательность, проверяющую состояния автомата, с использованием вначале X01=01, а затем X02=00.
Проверяющая последовательность начинается с Xs = 11, которая устанавливает автомат в начальное состояние 1. Затем X01=01 используется для идентификации состояний. Приложение X01 к автомату, находящемуся в состоянии 1, вызывает появление на выходе последовательности Y = 01. Прикладывая X01 повторно, проверяется 01 приемник начального состояния автомата.
Таблица 3.3 - Автомат А-3
Z (t) Z (t + 1), l (t) X=0X=112, 01, 123, 01, 131, 12, 0
С помощью переводящей последовательности Xп= переводим автомат из состояния 1 в 2. Прикладывая X01=1, получаем на выходе Y=00 и конечное состояние 2. Это конечное состояние проверяется X01=01 правильной реакцией автомата Y=00. Затем, автомат из состояния 2 с помощью Xп=0/0 переводится в 3, прикладывается X01=01 проверяется состояние 3 по выходной последовательности Y=11.
a) Отличительное дерево автомата А-3
б) Синхронизирующее дерево автомата А-3
Рисунок 3.3 - Отличительное и синхронизирующие деревья автомата А-3
Рассмотренная выше фаза идентификации состояний автомата А-3 представляется следующей последовательностью
X 11 01 01 0 01 01 0 01 01
Z 1 1 1 2 2 2 3 1 1 (3.6)
Y 01 01 0 00 00 0 11 01
Если автомат реагирует правильно на приложение входной последовательности, проверяющей правильность состояний автомата, то эта последовательность одновременно проверяет правильность переходов d (1,0) =2 и d (2,0) =3, которые используются для построения второй фазы эксперимента. Кроме того, анализ последовательности X / Z показывает, что в фазе проверки состояний автомата дополнительно проверяются переходы d (2,1) = 1, и d (3,1) =2, которые подчеркнуты в последовательности
X 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1
Z 1 2__1 2_1 2 3_2 3__2 3 1 1 2 1 (3.7)
Y 0 1 0 1 0 0 0 0 0 0 1 1 0 1
Анализ последовательности (3.7), проверяющей состояния автомата А-3 показывает, что в заключительной третьей фазе эксперимента проверки правильности переходов остается проверить лишь два перехода: d (1,1) =1 и d (3,0) =1. Так как после фазы идентификации состояний А-3 находится в состоянии 1, то для проверки перехода d (1,1) = 1 необходимо приложить последовательность 101 и проверить выходную последовательность 101. Перевести автомат с помощью Хп = из 1 в состояние 3, осуществить d (3,0) и, приложив отличительную последовательность X01=01, проверить правильность перехода d (3,0).
Полная проверяющая последовательность для А-3, включающая все три фазы эксперимента и состоящая из 24 входных символов представляется в виде:
X 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1
Z 1 2 1 2 1 2 3 2 3 2 3 1 1 2 1 1 2 1 2 3 1 2 1 (3.8)
Y 0 1 0 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1
Так как для автомата А-3 существует две отличительных последовательности, то эксперимент, построенный выше, не является единственным. Нетрудно убедиться, что более короткий эксперимент получается при использовании однородной отличительной последовательности X02=00. Это связано с тем, что X02 - преемники не совпадают с начальными состояниями. В этом случае полный проверяющий эксперимент для автомата А-3 представляется в виде:
X 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0
Z 1 2 3 1 2 3 1 2 3 2 3 1 1 2 3 2 1 2 3 (3.9)
Y 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0
Легко убедиться в том, что использование однородной отличительной последовательности сокращает длину эксперимента на 4 символа.
В эксперименте с автоматом, имеющим отличительные последовательности, считается, что в фазе идентификации состояний автомата проверяются все n состояний, если на выходе автомата появляется n различных последовательностей, как реакция на некоторую фиксированную входную последовательность [17].
В общем случае использование фиксированной входной последовательности в фазе идентификации состояний автомата является лишь необходимым условием проверки всех его состояний.
3.1.5 Отличительные последовательности в ОС
На функциональном уровне описания ячейки однородной одномерной сети без наблюдаемых выходов Х будем рассматривать ее таблицу истинности как таблица переходов - выходов автомата Мура, задаваемого тройкой (X,Y,d), у которого функции переходов и выходов совпадают, то есть
d (Zi,Xa) =l (Zi,Xa) =Zj,Zi, ZjZ, XaX, (3.10)
Пусть Z={Z1,…Zi,…Zn} - множество состояний автоматной модели ячейки сети. Будем обозначать Z [Zi] = { Z1,… Zi-1, Zi+1,…Zn } = { Z - Zi } - множество состояний ячейки сети, из которого исключен элемент Zi. Как было показано на примере одномерной сети (рисунок 1.2), при синтезе проверяющих тестов сложность решения задачи анализа полноты полученных тестов и их расширения связана с наличием в автоматной модели ячейки сети пар Xa - совместимых состояний. Из таблицы переходов ячейки легко можно определить множества Xi - совместимых состояний для каждого входного символ