Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА)
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
°чно определено по выходной последовательности l (Zi, Xu) для всех Zi Z.
В соответствии с определением 3.5 если автомат исправен и имеет установочную последовательность, то независимо от начального состояния его можно перевести в определенное состояние. Как показано в [15] любой минимальный автомат имеет установочную последовательность. Правила усечения дерева преемников автомата, приведенные в [10], позволяют построить установочное дерево по его таблице переходов-выходов, из которого определяется множество установочных последовательностей автомата.
Следует отметить, что каждая отличительная последовательность является установочной, в то время как обратное неверно.
3.1.3 Синхронизирующие последовательности
В [10] приведены методы синтеза синхронизирующих последовательностей (СП) по таблице переходов-выходов автомата и по функциональной схеме ДУ. В этом разделе определена верхняя граница длины СП, которая сравнивается с известными оценками [16], анализируется сложность построения СП и условия существования в автомате однородных синхронизирующих последовательностей.
Определение 3.6 Входная последовательность XS автомата, которая устанавливает его в определенное конечное состояние независимо от состояния выхода и начального состояния, называется синхронизирующей последовательностью.
Если автомат A (X, Y, Z, d, l) задан таблицей переходов-выходов, то из определения 3.6 следует, что автомат имеет синхронизирующую последовательность тогда и только тогда, когда существует входная последовательность Xs такая, что d (Zi, XS) =Z0; Zi Z, Z0 Z. Множество переходов d (Zi, XS) =Z0; для Zi Z, автомата определяет отображение множества его состояний Z в некоторое определенное состояние Z0 при подаче на автомат входной последовательности XS, то есть Z Z0.
Синхронизирующая последовательность для заданного автомата может быть найдена из синхронизирующего дерева, которое является деревом преемником, построенным по определенным правилам.
Так как синхронизирующая последовательность не связана с анализом выходной последовательности автомата, то функции выходов автомата не рассматриваются при построении синхронизирующего дерева. Вершины синхронизирующего дерева отмечаются s - множествами, коорые являются Xi-преемниками ( Xi X) состояний, входящих в s - множества предшествующих вершин. Вершина ранга j - синхронизирующего дерева является висячей, если:
а) вершина отмечается группой s - множеств, которая соответствует группе s - множеств какой-либо вершины ранга меньше j;
б) вершина j-го ранга отмечена одним простым s - множеством.
Путь в синхронизирующем дереве, корнем которого является начальное s - множество, включающее все состояния автомата, и завершающийся висячей вершиной, отмеченной единственным простым s - множеством, соответствует синхронизирующей последовательности автомата.
В качестве иллюстрации предлагается рассмотреть автомат А-2, заданный таблицей переходов-выходов (таблица 3.2). Синхронизирующее дерево (рисунок 3.2) является синхронизирующей последовательностью, которая устанавливает А-2 в состояние 4 независимо от начального состояния.
Таблица 3.2 - Автомат А-2
Z (t) Z (t + 1), l (t) X=0X=114, 12, 024, 13, 031, 04, 042, 01, 0
Рисунок 3.2 - Синхронизирующее дерево автомата А-2
3.1.4 Построение проверяющих последовательностей
Методы решения задач проверки ДУ, использующие явные и неявные модели ДУ, рассмотрены в [14, 10]. В качестве модели неисправности принята модель неисправности F1 и предполагается, что автомат является минимальным, сильносвязным, имеет отличительную последовательность и не меняет свое поведение в процессе эксперимента.
Для модели неисправности проверяющая последовательность состоит из 3-х частей или фаз:
а) установка в исходное начальное состояние;
б) проверка (идентификация) состояний;
в) проверка правильности переходов.
Первая фаза эксперимента может быть условной и безусловной. Если автомат имеет синхронизирующую последовательность (СП), то первая фаза безусловна. При отсутствии СП установка в начальное состояние осуществляется условным установочным экспериментом. В начале подается отличительная последовательность и по наблюдаемой реакции автомата определяется его конечное состояние. Затем автомат переводится в желаемое начальное состояние путем приложения соответствующей переводящей последовательности.
Фаза идентификации состояний заключается в попеременном приложении отличительной X0 и переводящих последовательностей Xп, определении реакции автомата на X0 для каждого начального состояния и определении X0-преемника каждого состояния. Фиксированная последовательность, идентифицирующая состояния автомата содержит n различных выходных последовательностей для всех состояний.
В третьей фазе эксперимента проверяются все m x n переходов автомата, каждое состояние до перехода и после перехода идентифицируется X0. Сокращение длины проверяющей последовательности достигается за счет совмещения второй и третьей фазы эксперимента [14].
Другой путь сокращения длины проверяющей последовательности заключается в использовании однородных от?/p>