3.2 Модифицированный метод построения полного проверяющего теста относительно модели неисправности <S, (£,≁), Â_m>

Алгоритм 3. Построение полного проверяющего теста относительно модели неисправности <S, (£,≁),Â_m >

Вход: Полностью определенный автомат Sи верхняя граница m числа состояний любой реализации S

Выход: Полный проверяющий тест TS относительно модели неисправности <S, (£,≁),Â_m >

Шаг 1. Построим усеченное дерево преемников автомата спецификации S. Корнем дерева на нулевом уровне является начальное состояние s0 автомата S; вершины дерева помечены подмножествами состояний автомата S . Пусть уже построены j уровней дерева, j³ 0. Для заданной нетерминальной вершины j^го уровня, помеченной подмножеством состояний К, и для заданного входного символа i, в дереве есть ребра, помеченные символом i, в вершину, помеченную i-преемниками подмножества К. Текущая вершина Current на k^м уровне, k > 0, помеченная подмножеством К состояний из множества S, объявляется листом дерева, если путь из корня в вершину Current содержит:

· 2^(|^K^|-|^P^|)^×^m+n вершин, помеченных подмножествами множества К, если s₀ÏK или s₀ÎK и s₀ÎP;

· 2^(|^K^|-|^P^|)^×^m^-1+n+1вершин, помеченных подмножествами множества К, если s₀ÎK и s₀ÏP;

где P – это такое подмножество состояний из множества K, что до некоторого l^го уровня (l< k) перебраны все возможные подмножества P, а n– это количество вершин на данном пути, помеченных подмножествами К, содержащими подмножества P, которые находятся на уровнях не ниже l^го уровня дерева (если P = Æ, то n= 0). Множество P строится итеративно:

1. P = Æ;

2. P= PÈP_i для каждого подмножества P_iмножества K, для которого путь из корня в вершину Current содержит (2^|^Pⁱ^|^×^m-1) вершин, помеченных подмножествами P_i (или (2^|^Pⁱ^|^×^m^-1) вершин в случае s0ÎP_i);

3. P= PÈP_j для всех существующих пар P_iÎP и P_jÏP (P_jÌK) таких, что P_iÇP_j= Q и путь из корня в вершину Current содержит (2^(|^Pj^|-|^Q^|)^×^m-1) вершин, помеченных подмножествами P_j, если s0ÏP_j или s0ÎQ, либо (2^(|^Pj^|-|^Q^|)^×^m^-1) вершин в случае s0ÎP_j.

Шаг 2. Включаем в TS каждую входную последовательность, которая помечает путь из корня к листу в усеченном дереве.

Теорема 2.

Для заданного эталонного автомата S и целого числа m алгоритм 3 доставляет полный проверяющий тест относительно модели неисправности <S, (£,≁),Â_m >.

Доказательство.

1. Рассмотрим самый общий случай – подмножество K состояний из множества S, и начальное состояние s₀ÏK. Согласно алгоритму 1, вершина усеченного дерева преемников Tree_S, помеченная подмножеством K, объявляется листом дерева, если путь из корня в эту вершину содержит 2^|^K^|^×^m вершин, помеченных подмножествами множества К. Это соответствует перебору всех возможных подмножеств К¢в усеченном дереве приемников Tree_S__T, построенному по пересечению эталонного автомата S и некоторой реализации T, где К¢ – это подмножество состояний пересечения S Tтаких, что первый символ каждой пары из К¢ содержится в К.

Предположим, что существует такое подмножество состояний P из множества K, что до некоторого l^го уровня дерева на пути из корня в вершину Current перебраны все возможные подмножества P. Множество P строится итеративно следующим образом:

Шаг 1. P = Æ.

Шаг 2. P= PÈP_i для каждого подмножества P_iмножества K, для которого путь из корня в вершину Current содержит (2^|^Pⁱ^|^×^m-1) вершин, помеченных подмножествами P_i. Добавление каждого такого P_i в множество P справедливо, т.к. если путь содержит указанное количество повторов, то этим перебираются все возможные варианты подмножеств P_i.

Шаг 3. P= PÈP_j для всех существующих пар P_iÎP и P_jÏP (P_jÌK) таких, что P_iÇP_j= Q и путь из корня в вершину Current содержит (2^(|^Pj^|-|^Q^|)^×^m-1) вершин, помеченных подмножествами P_j. В данном случае P_i уже было добавлено в Pна шаге 2, и для него уже встретилось (2^|^Pⁱ^|^×^m-1) вершин, помеченных подмножествами P_i. Следовательно, для P_j, пересекающегося с P_i, на данном пути дерева уже точно содержится (2^|^Q^|^×^m-1) вершин, помеченных подмножествами P_j, значит для того, чтобы были перебраны все варианты подмножеств P_j, достаточно встретить еще (2^(|^Pj^|-|^Q^|)^×^m-1) вершин.

Для построенного таким образом P(если P¹Æ) на соответствующем пути в дереве Tree_S__Tбудут перебраны все возможные подмножества P¢ (P¢ – это подмножество состояний S Tтаких, что первый символ каждой пары из P¢ содержится в P). Значит, далее на данном пути в дереве Tree_S__Tиз рассмотрения можно исключить вершины, помеченные подмножествами К¢, которые содержат подмножества P¢– поэтому рассматриваемых вершин, помеченных подмножествами K, не содержащих подмножеств P, будет 2^(|^K^|-|^P^|)^×^m . Но также необходимо учесть все n вершин, помеченных подмножествами К, содержащими подмножества P, которые встретились на рассматриваемом пути в дереве Tree_S выше, чем l^й уровень, т.к. из данных вершин подмножества P исключать не можем. Следовательно, количество вершин, помеченных подмножествами K, для усечения дерева в таком случае составляет 2^(|^K^|-|^P^|)^×^m+n вершин.

2. Далее рассмотрим случай, когда s₀ÎK, но s₀ не принадлежит множеству P. По алгоритму 1 для случая s₀ÎK вершина, помеченная подмножеством K, объявляется листом, если путь из корня в данную вершину содержит (2^|^K^|^×^m^-1+1) вершин, помеченных подмножествами множества K. Если же на данном пути для каждого P_iÎP встретилось, как и в предыдущем случае, необходимое число вершин, помеченных подмножествами P_i, то листовой будет являться вершина, путь из корня в которую содержит 2^(|^K^|-|^P^|)^×^m^-1+n+1 вершин, помеченных подмножествами K.

3. Если s₀ÎK и s₀ÎP, т.е.s₀ принадлежит одному из подмножеств P_jÎP, то необходимо, чтобы на рассматриваемом пути дерева встретилось (2^|^Pj^|^×^m^-1) вершин, помеченных подмножествами P_j, если P_jдобавляется к P на шаге 2 построения множества P, либо (2^(|^Pj^|-|^Q^|)^×^m^-1) вершин – если на шаге 3. Для остальных подмножеств P_i из P требуется встретить такое же количество вершин, как и в случае 1.Тогда можно исключить подмножества P из вершин, помеченных подмножествами K начиная с l^го уровня, и вершина, помеченная подмножеством K, объявляется листом, если путь из корня в данную вершину содержит 2^(|^K^|-|^P^|)^×^m+n вершин, помеченных подмножествами множества K.

4. Если для данного пути дерева P = Æ, то |P| = 0, n= 0 и пользуемся алгоритмом 2.

На рисунке 9 представлено усеченное дерево преемников для спецификации, изображенной на рис. 5, построенное согласно алгоритму 3. Суммарная длина полного проверяющего теста в этом случае составляет 200 символов, что на 77 символов меньше, чем для алгоритма 2.

Рисунок 9 – Усеченное дерево преемников, построенное по алгоритму 3

ЗАКЛЮЧЕНИЕ

В данной работе изучен метод построения тестов для недетерминированных автоматов относительно модели "черного ящика", предложенный в работе [1]. Этот метод, в отличие от других методов синтеза тестов для недетерминированных автоматов, не ориентирован на выполнение предположения "о всех погодных условиях". Исследованы возможные подходы к улучшению рассмотренного метода и предложена модификация данного метода. Показано, что тест, построенный согласно модифицированному методу, будет по-прежнему полным, но при этом менее избыточным.

ЛИТЕРАТУРА

1. Natalia Shabaldina, Khaled El-Fakih, Nina Yevtushenko. Testing Nondeterministic Finite State Machines With Respect to the Separability Relation. Lecture Notes in Computer Science, 2007(4581), pp. 305-318.

2. Шабалдина Н.В., Евтушенко Н.В. Построение тестов для конечных автоматов относительно неразделимости. Вестник ТГУ. Приложение. Серия "Математика. Кибернетика. Информатика". 2007. № 23. С. 287– 290.

3. Евтушенко Н.В., Петренко А.Ф., Ветрова М.В. Недетерминированные автоматы: анализ и синтез. Ч. 1. Отношения и операции. – Томск: Томский государственный университет, 2006. – 142 с.

4. Евтушенко Н.В., Спицина Н.В. О верхней оценке длины разделяющей последовательности

Модификация метода построения тестов для конечных автоматов относительно неразделимости (стр. 3 из 3)

3.2 Модифицированный метод построения полного проверяющего теста относительно модели неисправности <S, (£,≁), Âm>

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

3.2 Модифицированный метод построения полного проверяющего теста относительно модели неисправности <S, (£,≁), Â_m>