Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА)
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ния отличительного дерева установлено, что автомат не имеет отличительной последовательности.
Известно, что необходимым условием существования для данного автомата отличительной последовательности является свойство минимальности автомата. Однако это условие не является достаточным, так как существуют минимальные автоматы, не имеющие отличительных последовательностей.
В этом подразделе определены достаточные условия существования для заданного автомата отличительной последовательности, а также найдены оценки наименьшей верхней и нижней границы длины минимальной отличительной последовательности.
Определение 3.4 Входная последовательность X0 называется отличительной для автомата А= (X, Y, Z, d, l), если выходная последовательность автомата, как реакция на X0, различна для любого начального состояния, то есть
l (Zi, X0) l (Zi, X0), для Zi, Zj Z, Zi Zj. (3.2)
С целью определения достаточных условий существования для заданного автомата отличительной последовательности предлагается рассмотреть процедуру построения отличительного дерева и некоторые его свойства.
Отличительное дерево приемников, в котором вершина ранга r является висячей если:
а) ей поставлена в соответствие группа s - множеств, содержащая, по меньшей мере, одно кратное s - множество;
б) ей поставлена в соответствие группа s - множеств, в которой все не простые s - множества совпадают с s - множествами вершины ранга меньше r;
в) среди вершин ранга r имеется хотя бы одна вершина, отмеченная простым s - множеством.
Для иллюстрации воспользуемся примером автомата А-1, заданного таблицей 3.1 переходов-выходов. Отличительное дерево, построенное в соответствии с вышеприведенными правилами усечения дерева преемников, приведено на рисунке 3.1 Каждая вершина отмечена s - множествами, полученными в соответствии с правилами построения дерева преемников. Над каждым s - множеством в отличительном дереве указаны состояния предшественники, принадлежащие начальному s-множеству и порождающие соответствующие им группы s - множеств.
Таблица 3.1 - Автомат А-1
Z (t) Z (t + 1), l (t) X1X212, 11, 121, 13, 035, 03, 142, 01, 054, 15, 0
Рисунок 3.1 - Отличительное дерево автомата А-1
Отображение множества допустимых начальных состояний, принадлежащих начальному s - множеству, в группы s - множеств, которыми отмечены вершины отличительного дерева, полностью определяется функцией переходов-выходов автомата. Например, для автомата А-1
d ({ } X1) = { 2, 1, 4 }, { 5, 2 }. (3.3)
Блоки разбиения p1 ={} множества состояний A-1 определяют отношение эквивалентности состояний в том смысле, что состояния, принадлежащие каждому блоку разбиения p1 X1 - неразличимы, а сами блоки разбиения p1 являются X1 - различимыми. Вершине отличительного дерева (рисунок 3.1), отмеченной разбиением p1, поставлена в соответствие группа s - множеств s1: {2, 1, 4 },{ 5, 2}, включающих состояния, которые являются преемниками соответствующих состояний блоков разбиения p1.
В отличительном дереве автомата A-1 каждому s - множеству вершины дерева поставлено в соответствие p - разбиение множества начальных состояний, для которых состояния s - множеств являются конечными состояниями при приложении к входу автомата последовательности входных символов, соответствующих меткам дуг отличительного дерева. Путь в отличительном дереве от его корня до вершины, отмеченной группой простых s-множеств, определяет отличительную последовательность минимальной длины. Отличительная последовательность X0= (X1, X1, X1, X2, X1) автомата А-1 определяет следующую последовательность p - разбиений начальных состояний
p (1) p1 p2 p3 p3 p4 = p (0), (3.4)
которую можно упорядочить в виде
p (1) >p1 > p2 > p3 = p3 > p4 = p (0). (3.5)
Таким образом, проведенный выше анализ отличительного дерева автомата А-1 показал, что построение отличительного дерева сопровождается уменьшением числа неразличимых начальных состояний автомата, которым для каждого ранга отличительного дерева поставлено в соответствие p - разбиение, определяющее отношение эквивалентности состояний. Построение отличительного дерева автомата, имеющего отличительную последовательность, завершается вершиной, которой поставлено в соответствие 0 - разбиение множества начальных состояний p (0).
3.1.2 Установочные последовательности
В первой фазе диагностического эксперимента с автоматом предусматривается установка его в известное начальное состояние. Это достигается использованием установочных или синхронизирующих последовательностей [14, 10]. Методы построения условных и безусловных установочных экспериментов, а также синтез установочных синхронизирующих последовательностей достаточно полно и глубоко изложен в [10]. В этом разделе получена оценка сложности безусловного установочного эксперимента.
Определение 3.5 Входная последовательность Xu называется установочной для автомата (X, Y, Z, d, l), если его конечное состояние d (Zi,Xu) может быть однозн?/p>